Project

General

Profile

Actions

Feature #6362

closed

Modular exponentiation/inverse

Added by MartinBosslet (Martin Bosslet) over 12 years ago. Updated almost 4 years ago.

Status:
Closed
Target version:
-
[ruby-core:<unknown>]

Description

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?

Updated by sdaubert (Sylvain Daubert) over 12 years ago

+1 : very helpful for cryptographic stuffs.

Updated by mame (Yusuke Endoh) over 12 years ago

  • 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

Updated by MartinBosslet (Martin Bosslet) over 12 years ago

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

Updated by nobu (Nobuyoshi Nakada) over 12 years ago

=begin
What about a new class, say Modulo?

m = Modulo.new(101, 11)
m.to_i #=> 2
m**4 #=> 5
=end

Updated by mame (Yusuke Endoh) over 12 years ago

  • 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

Updated by MartinBosslet (Martin Bosslet) over 12 years ago

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

Actions #7

Updated by mame (Yusuke Endoh) almost 12 years ago

  • Target version set to 2.6

Updated by spastorino (Santiago Pastorino) over 11 years ago

This would be a great thing to have +1000

Actions #9

Updated by naruse (Yui NARUSE) almost 7 years ago

  • Target version deleted (2.6)

Updated by msnm (Masahiro Nomoto) about 5 years ago

FYI:

Updated by leahneukirchen (Leah Neukirchen) almost 4 years ago

As of Python 3.8, modular inverses are supported by Python's pow function, which can take a mod argument, just like Ruby's.
https://docs.python.org/3/library/functions.html#pow

I therefore propose to add this feature as

n.pow(-1, m)

This currently throws an error (Integer#pow() 1st argument cannot be negative when 2nd argument specified), so should be possible to extend.

Updated by nobu (Nobuyoshi Nakada) almost 4 years ago

  • Status changed from Assigned to Closed

Please file a new ticket.

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0