https://redmine.ruby-lang.org/https://redmine.ruby-lang.org/favicon.ico?17113305112012-04-27T03:05:27ZRuby Issue Tracking SystemRuby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=262242012-04-27T03:05:27Zsdaubert (Sylvain Daubert)sylvain.daubert@laposte.net
<ul></ul><p>+1 : very helpful for cryptographic stuffs.</p> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=262252012-04-27T03:10:43Zmame (Yusuke Endoh)mame@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Feedback</i></li><li><strong>Assignee</strong> set to <i>MartinBosslet (Martin Bosslet)</i></li></ul><p>Personally I like this proposal, but it seems to require:</p>
<ul>
<li>use cases (Well, personally I often use them for Project Euler :-)</li>
<li>candidates of method name (pow_mod / inv_mod?)</li>
<li>a detailed spec (especially corner cases, e.g., not coprime case, negative modulo, etc.)</li>
<li>a patch</li>
<li>other kinds of modular arithmetic are not needed? (add_mod, mul_mod, sqrt_mod, ...)</li>
</ul>
<p>--<br>
Yusuke Endoh <a href="mailto:mame@tsg.ne.jp" class="email">mame@tsg.ne.jp</a></p> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=262732012-04-28T09:32:22ZMartinBosslet (Martin Bosslet)Martin.Bosslet@gmail.com
<ul></ul><p>mame (Yusuke Endoh) wrote:</p>
<blockquote>
<p>Personally I like this proposal, but it seems to require:</p>
<ul>
<li>use cases (Well, personally I often use them for Project Euler :-)</li>
</ul>
</blockquote>
<p>It would be incredibly helpful when implementing cryptographic primitives.<br>
Apart from mathematics in general (and Project Euler in particular!) I have<br>
little experience with other areas where it would be equally useful. One<br>
could argue this should be in a gem, but since we already have excellent<br>
Bignum support, I'd enjoy to see it even more excellent :)</p>
<blockquote>
<ul>
<li>candidates of method name (pow_mod / inv_mod?)</li>
</ul>
</blockquote>
<p>Yes, I thought of them as well. If there would be no complaints...</p>
<blockquote>
<ul>
<li>other kinds of modular arithmetic are not needed? (add_mod, mul_mod, sqrt_mod, ...)</li>
</ul>
</blockquote>
<p>Seems the right thing to do. GCD, modular shifts, etc. as well. I'll explore what<br>
others like GMP or OpenSSL support and start from there.</p>
<blockquote>
<ul>
<li>a detailed spec (especially corner cases, e.g., not coprime case, negative modulo, etc.)</li>
</ul>
</blockquote>
<p>Based on what I find out, I'll try to design an interface plus specs. Another question is<br>
what particular algorithms to use for implementing each aspect. I'm currently catching<br>
up on literature, although I'd be happy about suggestions, of course!</p>
<blockquote>
<ul>
<li>a patch</li>
</ul>
</blockquote>
<p>Will do once there is a consensus on the specs!</p>
<p>-Martin</p> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=262932012-04-28T22:20:10Znobu (Nobuyoshi Nakada)nobu@ruby-lang.org
<ul></ul><p>=begin<br>
What about a new class, say Modulo?</p>
<p>m = Modulo.new(101, 11)<br>
m.to_i #=> 2<br>
m**4 #=> 5<br>
=end</p> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=264042012-05-03T12:03:01Zmame (Yusuke Endoh)mame@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Feedback</i> to <i>Assigned</i></li><li><strong>Assignee</strong> changed from <i>MartinBosslet (Martin Bosslet)</i> to <i>matz (Yukihiro Matsumoto)</i></li></ul><p>Martin, thanks. Assigning it to matz.</p>
<p>nobu wrote:</p>
<blockquote>
<p>What about a new class, say Modulo?</p>
</blockquote>
<p>I guess, it would be slow, and therefore defeat the purpose.<br>
But indeed it looks like the Ruby way.</p>
<p>Anyway, it mgiht be a good idea to start it with gem.</p>
<p>--<br>
Yusuke Endoh <a href="mailto:mame@tsg.ne.jp" class="email">mame@tsg.ne.jp</a></p> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=264712012-05-05T10:35:10ZMartinBosslet (Martin Bosslet)Martin.Bosslet@gmail.com
<ul></ul><p>mame (Yusuke Endoh) wrote:</p>
<blockquote>
<p>Martin, thanks. Assigning it to matz.</p>
</blockquote>
<p>Sure, you're welcome :)</p>
<blockquote>
<p>nobu wrote:</p>
<blockquote>
<p>What about a new class, say Modulo?</p>
</blockquote>
</blockquote>
<p>Sounds really nice and it would extend better to arithmetic<br>
in finite fields defined over irreducible polynomials or to<br>
elliptic curves. This is where the initial proposal would<br>
fall short eventually.</p>
<blockquote>
<p>I guess, it would be slow, and therefore defeat the purpose.<br>
But indeed it looks like the Ruby way.</p>
</blockquote>
<p>Just for my understanding, why do you think it would be slow?<br>
If it were written in C with access to Bignum internal representation,<br>
would it still be slow?</p>
<blockquote>
<p>Anyway, it mgiht be a good idea to start it with gem.</p>
</blockquote>
<p>So there's no need for a spec right now, or would you still be<br>
interested?</p>
<p>-Martin</p> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=332972012-11-20T22:42:16Zmame (Yusuke Endoh)mame@ruby-lang.org
<ul><li><strong>Target version</strong> set to <i>2.6</i></li></ul> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=358302013-02-05T04:23:18Zspastorino (Santiago Pastorino)santiago@wyeworks.com
<ul></ul><p>This would be a great thing to have +1000</p> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=687732017-12-25T18:15:05Znaruse (Yui NARUSE)naruse@airemix.jp
<ul><li><strong>Target version</strong> deleted (<del><i>2.6</i></del>)</li></ul> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=823882019-10-31T04:23:55Zmsnm (Masahiro Nomoto)
<ul></ul><p>FYI:</p>
<ul>
<li>Modular exponentiation is implemented in Ruby 2.5 . <a href="https://ruby-doc.org/core/Integer.html#method-i-pow" class="external">https://ruby-doc.org/core/Integer.html#method-i-pow</a>
</li>
<li>I created a patch gem to calculate a usual/modular multiplicative inverse. <a href="https://www.rubydoc.info/gems/numeric_inverse" class="external">https://www.rubydoc.info/gems/numeric_inverse</a>
</li>
<li>In heavy use, OpenSSL::BN is useful. <a href="https://ruby-doc.org/stdlib/libdoc/openssl/rdoc/OpenSSL/BN.html" class="external">https://ruby-doc.org/stdlib/libdoc/openssl/rdoc/OpenSSL/BN.html</a>
</li>
</ul> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=897322021-01-03T19:35:18Zleahneukirchen (Leah Neukirchen)
<ul></ul><p>As of Python 3.8, modular inverses are supported by Python's pow function, which can take a mod argument, just like Ruby's.<br>
<a href="https://docs.python.org/3/library/functions.html#pow" class="external">https://docs.python.org/3/library/functions.html#pow</a></p>
<p>I therefore propose to add this feature as</p>
<pre><code>n.pow(-1, m)
</code></pre>
<p>This currently throws an error (<code>Integer#pow() 1st argument cannot be negative when 2nd argument specified</code>), so should be possible to extend.</p> Ruby master - Feature #6362: Modular exponentiation/inversehttps://redmine.ruby-lang.org/issues/6362?journal_id=897382021-01-04T01:42:09Znobu (Nobuyoshi Nakada)nobu@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Assigned</i> to <i>Closed</i></li></ul><p>Please file a new ticket.</p>