[ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse

[ruby-core:44631] [ruby-trunk - Feature #6362][Open] Modular exponentiation/inverse

[MartinBosslet (Martin Bosslet)]

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/

[ruby-core:44657] [ruby-trunk - Feature #6362] Modular exponentiation/inverse

[sdaubert (Sylvain Daubert)]

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/

[ruby-core:44658] [ruby-trunk - Feature #6362][Feedback] Modular exponentiation/inverse

[mame (Yusuke Endoh)]

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/

[ruby-core:44712] [ruby-trunk - Feature #6362] Modular exponentiation/inverse

[MartinBosslet (Martin Bosslet)]

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/

[ruby-core:44733] [ruby-trunk - Feature #6362] Modular exponentiation/inverse

[nobu (Nobuyoshi Nakada)]

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/

[ruby-core:44829] [ruby-trunk - Feature #6362][Assigned] Modular exponentiation/inverse

[mame (Yusuke Endoh)]

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/

[ruby-core:44888] [ruby-trunk - Feature #6362] Modular exponentiation/inverse

[MartinBosslet (Martin Bosslet)]

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/

[ruby-core:51848] [ruby-trunk - Feature #6362] Modular exponentiation/inverse

[spastorino (Santiago Pastorino)]

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/

[ruby-core:95599] [Ruby master Feature#6362] Modular exponentiation/inverse

[a2him2no4rst]

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/