* [ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse
@ 2012-04-26 0:52 MartinBosslet (Martin Bosslet)
2012-04-26 18:05 ` [ruby-core:44657] [ruby-trunk - Feature #6362] " sdaubert (Sylvain Daubert)
` (7 more replies)
0 siblings, 8 replies; 9+ messages in thread
From: MartinBosslet (Martin Bosslet) @ 2012-04-26 0:52 UTC (permalink / raw)
To: ruby-core
Issue #6362 has been reported by MartinBosslet (Martin Bosslet).
----------------------------------------
Feature #6362: Modular exponentiation/inverse
https://bugs.ruby-lang.org/issues/6362
Author: MartinBosslet (Martin Bosslet)
Status: Open
Priority: Normal
Assignee:
Category: core
Target version:
I'd like to ask your opinion about adding two methods for modular
exponentiation/modular inverse to integer classes. Is this
functionality too specific or would this be a welcome addition?
--
http://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:44657] [ruby-trunk - Feature #6362] Modular exponentiation/inverse
2012-04-26 0:52 [ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse MartinBosslet (Martin Bosslet)
@ 2012-04-26 18:05 ` sdaubert (Sylvain Daubert)
2012-04-26 18:10 ` [ruby-core:44658] [ruby-trunk - Feature #6362][Feedback] " mame (Yusuke Endoh)
` (6 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: sdaubert (Sylvain Daubert) @ 2012-04-26 18:05 UTC (permalink / raw)
To: ruby-core
Issue #6362 has been updated by sdaubert (Sylvain Daubert).
+1 : very helpful for cryptographic stuffs.
----------------------------------------
Feature #6362: Modular exponentiation/inverse
https://bugs.ruby-lang.org/issues/6362#change-26224
Author: MartinBosslet (Martin Bosslet)
Status: Open
Priority: Normal
Assignee:
Category: core
Target version:
I'd like to ask your opinion about adding two methods for modular
exponentiation/modular inverse to integer classes. Is this
functionality too specific or would this be a welcome addition?
--
http://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:44658] [ruby-trunk - Feature #6362][Feedback] Modular exponentiation/inverse
2012-04-26 0:52 [ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse MartinBosslet (Martin Bosslet)
2012-04-26 18:05 ` [ruby-core:44657] [ruby-trunk - Feature #6362] " sdaubert (Sylvain Daubert)
@ 2012-04-26 18:10 ` mame (Yusuke Endoh)
2012-04-28 0:32 ` [ruby-core:44712] [ruby-trunk - Feature #6362] " MartinBosslet (Martin Bosslet)
` (5 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: mame (Yusuke Endoh) @ 2012-04-26 18:10 UTC (permalink / raw)
To: ruby-core
Issue #6362 has been updated by mame (Yusuke Endoh).
Status changed from Open to Feedback
Assignee set to MartinBosslet (Martin Bosslet)
Personally I like this proposal, but it seems to require:
- use cases (Well, personally I often use them for Project Euler :-)
- candidates of method name (pow_mod / inv_mod?)
- a detailed spec (especially corner cases, e.g., not coprime case, negative modulo, etc.)
- a patch
- other kinds of modular arithmetic are not needed? (add_mod, mul_mod, sqrt_mod, ...)
--
Yusuke Endoh <mame@tsg.ne.jp>
----------------------------------------
Feature #6362: Modular exponentiation/inverse
https://bugs.ruby-lang.org/issues/6362#change-26225
Author: MartinBosslet (Martin Bosslet)
Status: Feedback
Priority: Normal
Assignee: MartinBosslet (Martin Bosslet)
Category: core
Target version:
I'd like to ask your opinion about adding two methods for modular
exponentiation/modular inverse to integer classes. Is this
functionality too specific or would this be a welcome addition?
--
http://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:44712] [ruby-trunk - Feature #6362] Modular exponentiation/inverse
2012-04-26 0:52 [ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse MartinBosslet (Martin Bosslet)
2012-04-26 18:05 ` [ruby-core:44657] [ruby-trunk - Feature #6362] " sdaubert (Sylvain Daubert)
2012-04-26 18:10 ` [ruby-core:44658] [ruby-trunk - Feature #6362][Feedback] " mame (Yusuke Endoh)
@ 2012-04-28 0:32 ` MartinBosslet (Martin Bosslet)
2012-04-28 13:20 ` [ruby-core:44733] " nobu (Nobuyoshi Nakada)
` (4 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: MartinBosslet (Martin Bosslet) @ 2012-04-28 0:32 UTC (permalink / raw)
To: ruby-core
Issue #6362 has been updated by MartinBosslet (Martin Bosslet).
mame (Yusuke Endoh) wrote:
> Personally I like this proposal, but it seems to require:
>
> - use cases (Well, personally I often use them for Project Euler :-)
It would be incredibly helpful when implementing cryptographic primitives.
Apart from mathematics in general (and Project Euler in particular!) I have
little experience with other areas where it would be equally useful. One
could argue this should be in a gem, but since we already have excellent
Bignum support, I'd enjoy to see it even more excellent :)
> - candidates of method name (pow_mod / inv_mod?)
Yes, I thought of them as well. If there would be no complaints...
> - other kinds of modular arithmetic are not needed? (add_mod, mul_mod, sqrt_mod, ...)
Seems the right thing to do. GCD, modular shifts, etc. as well. I'll explore what
others like GMP or OpenSSL support and start from there.
> - a detailed spec (especially corner cases, e.g., not coprime case, negative modulo, etc.)
Based on what I find out, I'll try to design an interface plus specs. Another question is
what particular algorithms to use for implementing each aspect. I'm currently catching
up on literature, although I'd be happy about suggestions, of course!
> - a patch
Will do once there is a consensus on the specs!
-Martin
----------------------------------------
Feature #6362: Modular exponentiation/inverse
https://bugs.ruby-lang.org/issues/6362#change-26273
Author: MartinBosslet (Martin Bosslet)
Status: Feedback
Priority: Normal
Assignee: MartinBosslet (Martin Bosslet)
Category: core
Target version:
I'd like to ask your opinion about adding two methods for modular
exponentiation/modular inverse to integer classes. Is this
functionality too specific or would this be a welcome addition?
--
http://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:44733] [ruby-trunk - Feature #6362] Modular exponentiation/inverse
2012-04-26 0:52 [ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse MartinBosslet (Martin Bosslet)
` (2 preceding siblings ...)
2012-04-28 0:32 ` [ruby-core:44712] [ruby-trunk - Feature #6362] " MartinBosslet (Martin Bosslet)
@ 2012-04-28 13:20 ` nobu (Nobuyoshi Nakada)
2012-05-03 3:03 ` [ruby-core:44829] [ruby-trunk - Feature #6362][Assigned] " mame (Yusuke Endoh)
` (3 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: nobu (Nobuyoshi Nakada) @ 2012-04-28 13:20 UTC (permalink / raw)
To: ruby-core
Issue #6362 has been updated by nobu (Nobuyoshi Nakada).
=begin
What about a new class, say Modulo?
m = Modulo.new(101, 11)
m.to_i #=> 2
m**4 #=> 5
=end
----------------------------------------
Feature #6362: Modular exponentiation/inverse
https://bugs.ruby-lang.org/issues/6362#change-26293
Author: MartinBosslet (Martin Bosslet)
Status: Feedback
Priority: Normal
Assignee: MartinBosslet (Martin Bosslet)
Category: core
Target version:
I'd like to ask your opinion about adding two methods for modular
exponentiation/modular inverse to integer classes. Is this
functionality too specific or would this be a welcome addition?
--
http://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:44829] [ruby-trunk - Feature #6362][Assigned] Modular exponentiation/inverse
2012-04-26 0:52 [ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse MartinBosslet (Martin Bosslet)
` (3 preceding siblings ...)
2012-04-28 13:20 ` [ruby-core:44733] " nobu (Nobuyoshi Nakada)
@ 2012-05-03 3:03 ` mame (Yusuke Endoh)
2012-05-05 1:35 ` [ruby-core:44888] [ruby-trunk - Feature #6362] " MartinBosslet (Martin Bosslet)
` (2 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: mame (Yusuke Endoh) @ 2012-05-03 3:03 UTC (permalink / raw)
To: ruby-core
Issue #6362 has been updated by mame (Yusuke Endoh).
Status changed from Feedback to Assigned
Assignee changed from MartinBosslet (Martin Bosslet) to matz (Yukihiro Matsumoto)
Martin, thanks. Assigning it to matz.
nobu wrote:
> What about a new class, say Modulo?
I guess, it would be slow, and therefore defeat the purpose.
But indeed it looks like the Ruby way.
Anyway, it mgiht be a good idea to start it with gem.
--
Yusuke Endoh <mame@tsg.ne.jp>
----------------------------------------
Feature #6362: Modular exponentiation/inverse
https://bugs.ruby-lang.org/issues/6362#change-26404
Author: MartinBosslet (Martin Bosslet)
Status: Assigned
Priority: Normal
Assignee: matz (Yukihiro Matsumoto)
Category: core
Target version:
I'd like to ask your opinion about adding two methods for modular
exponentiation/modular inverse to integer classes. Is this
functionality too specific or would this be a welcome addition?
--
http://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:44888] [ruby-trunk - Feature #6362] Modular exponentiation/inverse
2012-04-26 0:52 [ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse MartinBosslet (Martin Bosslet)
` (4 preceding siblings ...)
2012-05-03 3:03 ` [ruby-core:44829] [ruby-trunk - Feature #6362][Assigned] " mame (Yusuke Endoh)
@ 2012-05-05 1:35 ` MartinBosslet (Martin Bosslet)
2013-02-04 19:24 ` [ruby-core:51848] " spastorino (Santiago Pastorino)
2019-10-31 4:23 ` [ruby-core:95599] [Ruby master Feature#6362] " a2him2no4rst
7 siblings, 0 replies; 9+ messages in thread
From: MartinBosslet (Martin Bosslet) @ 2012-05-05 1:35 UTC (permalink / raw)
To: ruby-core
Issue #6362 has been updated by MartinBosslet (Martin Bosslet).
mame (Yusuke Endoh) wrote:
> Martin, thanks. Assigning it to matz.
Sure, you're welcome :)
> nobu wrote:
> > What about a new class, say Modulo?
Sounds really nice and it would extend better to arithmetic
in finite fields defined over irreducible polynomials or to
elliptic curves. This is where the initial proposal would
fall short eventually.
> I guess, it would be slow, and therefore defeat the purpose.
> But indeed it looks like the Ruby way.
Just for my understanding, why do you think it would be slow?
If it were written in C with access to Bignum internal representation,
would it still be slow?
> Anyway, it mgiht be a good idea to start it with gem.
>
So there's no need for a spec right now, or would you still be
interested?
-Martin
----------------------------------------
Feature #6362: Modular exponentiation/inverse
https://bugs.ruby-lang.org/issues/6362#change-26471
Author: MartinBosslet (Martin Bosslet)
Status: Assigned
Priority: Normal
Assignee: matz (Yukihiro Matsumoto)
Category: core
Target version:
I'd like to ask your opinion about adding two methods for modular
exponentiation/modular inverse to integer classes. Is this
functionality too specific or would this be a welcome addition?
--
http://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:51848] [ruby-trunk - Feature #6362] Modular exponentiation/inverse
2012-04-26 0:52 [ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse MartinBosslet (Martin Bosslet)
` (5 preceding siblings ...)
2012-05-05 1:35 ` [ruby-core:44888] [ruby-trunk - Feature #6362] " MartinBosslet (Martin Bosslet)
@ 2013-02-04 19:24 ` spastorino (Santiago Pastorino)
2019-10-31 4:23 ` [ruby-core:95599] [Ruby master Feature#6362] " a2him2no4rst
7 siblings, 0 replies; 9+ messages in thread
From: spastorino (Santiago Pastorino) @ 2013-02-04 19:24 UTC (permalink / raw)
To: ruby-core
Issue #6362 has been updated by spastorino (Santiago Pastorino).
This would be a great thing to have +1000
----------------------------------------
Feature #6362: Modular exponentiation/inverse
https://bugs.ruby-lang.org/issues/6362#change-35830
Author: MartinBosslet (Martin Bosslet)
Status: Assigned
Priority: Normal
Assignee: matz (Yukihiro Matsumoto)
Category: core
Target version: next minor
I'd like to ask your opinion about adding two methods for modular
exponentiation/modular inverse to integer classes. Is this
functionality too specific or would this be a welcome addition?
--
http://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:95599] [Ruby master Feature#6362] Modular exponentiation/inverse
2012-04-26 0:52 [ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse MartinBosslet (Martin Bosslet)
` (6 preceding siblings ...)
2013-02-04 19:24 ` [ruby-core:51848] " spastorino (Santiago Pastorino)
@ 2019-10-31 4:23 ` a2him2no4rst
7 siblings, 0 replies; 9+ messages in thread
From: a2him2no4rst @ 2019-10-31 4:23 UTC (permalink / raw)
To: ruby-core
Issue #6362 has been updated by msnm (Masahiro Nomoto).
FYI:
* Modular exponentiation is implemented in Ruby 2.5 . https://ruby-doc.org/core/Integer.html#method-i-pow
* I created a gem to calculate a usual/modular multiplicative inverse. https://www.rubydoc.info/gems/numeric_inverse
* In heavy use, OpenSSL::BN is useful. https://ruby-doc.org/stdlib/libdoc/openssl/rdoc/OpenSSL/BN.html
----------------------------------------
Feature #6362: Modular exponentiation/inverse
https://bugs.ruby-lang.org/issues/6362#change-82388
* Author: MartinBosslet (Martin Bosslet)
* Status: Assigned
* Priority: Normal
* Assignee: matz (Yukihiro Matsumoto)
* Target version:
----------------------------------------
I'd like to ask your opinion about adding two methods for modular
exponentiation/modular inverse to integer classes. Is this
functionality too specific or would this be a welcome addition?
--
https://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2019-10-31 4:24 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-04-26 0:52 [ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse MartinBosslet (Martin Bosslet)
2012-04-26 18:05 ` [ruby-core:44657] [ruby-trunk - Feature #6362] " sdaubert (Sylvain Daubert)
2012-04-26 18:10 ` [ruby-core:44658] [ruby-trunk - Feature #6362][Feedback] " mame (Yusuke Endoh)
2012-04-28 0:32 ` [ruby-core:44712] [ruby-trunk - Feature #6362] " MartinBosslet (Martin Bosslet)
2012-04-28 13:20 ` [ruby-core:44733] " nobu (Nobuyoshi Nakada)
2012-05-03 3:03 ` [ruby-core:44829] [ruby-trunk - Feature #6362][Assigned] " mame (Yusuke Endoh)
2012-05-05 1:35 ` [ruby-core:44888] [ruby-trunk - Feature #6362] " MartinBosslet (Martin Bosslet)
2013-02-04 19:24 ` [ruby-core:51848] " spastorino (Santiago Pastorino)
2019-10-31 4:23 ` [ruby-core:95599] [Ruby master Feature#6362] " a2him2no4rst
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).