## Feature #6362

### Modular exponentiation/inverse

Status: | Assigned | ||
---|---|---|---|

Priority: | Normal | ||

Assignee: | Yukihiro Matsumoto |

**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?

### History

#### #1 Updated by Sylvain Daubert over 3 years ago

+1 : very helpful for cryptographic stuffs.

#### #2 Updated by Yusuke Endoh over 3 years ago

**Status**changed from*Open*to*Feedback***Assignee**set to*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

#### #3 Updated by Martin Bosslet over 3 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

#### #4 Updated by Nobuyoshi Nakada over 3 years ago

=begin

What about a new class, say Modulo?

m = Modulo.new(101, 11)

m.to_i #=> 2

m**4 #=> 5

=end

#### #5 Updated by Yusuke Endoh over 3 years ago

**Status**changed from*Feedback*to*Assigned***Assignee**changed from*Martin Bosslet*to*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

#### #6 Updated by Martin Bosslet over 3 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

#### #7 Updated by Yusuke Endoh almost 3 years ago

**Target version**set to*next minor*

#### #8 Updated by Santiago Pastorino over 2 years ago

This would be a great thing to have +1000