Modular exponentiation and inverse are the two functions cryptographers wish were primitives.
On Tue, Apr 4, 2023 at 11:07 AM Henry Rich <[email protected]> wrote: > Expect primitive support for modular inverse in an upcoming beta. > > Henry Rich > > > On Tue, Apr 4, 2023, 1:49 PM 'Michael Day' via Programming < > [email protected]> wrote: > > > Thanks, Chris, and Cliff too. > > > > Yes, a mod inverse helps a lot. Once you've got an inverse, it's easy > > to derive a modular divide, or vice > > versa. > > > > inversep in primutil.ijs is well defined for a prime modulus - the name > > "primutil" does of course imply > > a prime modulus. > > inversep also appears to work ok for those numbers in the ring of > > integers modulo non-prime modulus. > > > > eg members of the ring modulo 10 are {1 3 7 9} > > {{ y,:y (10 mtimes) (10&inversep)"0 y}} 1 3 7 9 > > 1 3 7 9 > > 1 1 1 1 > > {{ y,:y (10 mtimes) (10&mrecip)"0 y}} 1 3 7 9 > > 1 3 7 9 > > 1 1 1 1 > > > > I find rather better performance with my mrecip: > > ts =: 6!:2 , 7!:2@] > > > > 1 p: 1000000009 > > 1 > > > > ts'100000009 mrecip 999999000 + >:i.1007' > > 0.0061255 22592 > > ts'100000009 inversep"0] 999999000 + >:i.1007' > > 0.0798054 97160 > > ts'100000009 mi"0] 999999000 + >:i.1007' > > 0.0908823 174192 > > > > A bit surprising as the Extended Euler Algorithm is supposed to be best > > for getting a modular inverse. > > > > 1000000009 (mrecip-:inversep"0) 999999000 + >:i.1007 > > 1 > > 1000000009 ((1000000009 mi)"0 @] -:inversep"0) 999999000 + >:i.1007 > > 1 > > > > Here's mrecip: > > > > mrecip =: {{ > > y (x&|@^) <: 5 p: x > > }}"0 > > > > As for inversep, and Cliff's mi, mrecip is well-defined for prime x, > > and also for composite > > x for y in x's ring, ie where 1 = x +. y > > > > Results are NOT reliable for arguments not coprime with the modulus. > > > > Thanks, > > > > Mike > > > > On 03/04/2023 16:22, chris burke wrote: > > > Cliff > > > > > > There are some mod functions in the math/misc addon, e.g. this gives > > > Mike Day's table > > > > > > load 'math/misc/primutil' > > > f=: (17 timesmod) (17&inversep) > > > 2 3 4 f"0 table >:i.8 > > > +---+---------------------+ > > > |f"0|1 2 3 4 5 6 7 8| > > > +---+---------------------+ > > > |2 |2 1 12 9 14 6 10 13| > > > |3 |3 10 1 5 4 9 15 11| > > > |4 |4 2 7 1 11 12 3 9| > > > +---+---------------------+ > > > > > > Any improvements welcome, thanks. > > > > > > Chris > > > > > > On Mon, Apr 3, 2023 at 5:49 AM Clifford Reiter<[email protected]> > > wrote: > > >> I dug up an old extended gcd to build an adverb for modular divide > > >> > > >> NB. Find the gcd of two numbers > > >> > > >> NB. and coef giving gcd as a linear combination of y > > >> > > >> gcd2x=: 3 : 0 > > >> > > >> 'r0 r1'=.y > > >> > > >> 's0 s1'=.1 0x > > >> > > >> 't0 t1'=.0 1x > > >> > > >> while. r1 ~: 0 do. > > >> > > >> q=. r0 <.@% r1 > > >> > > >> 'r0 r1'=. r1,r0-q*r1 > > >> > > >> 's0 s1'=. s1,s0-q*s1 > > >> > > >> 't0 t1'=. t1,t0-q*t1 > > >> > > >> end. > > >> > > >> r0,s0,t0 > > >> > > >> ) > > >> > > >> gcd2x 51 119 > > >> > > >> 17 _2 1 > > >> > > >> _2 1 +/ . * 51 119 > > >> > > >> 17 > > >> > > >> NB. adverb giving divide (inverse) mod m > > >> > > >> mi=:1 : 0"0 > > >> > > >> 'r0 s0 t0'=:gcd2x m,y > > >> > > >> if. r0=1 do. m|t0 else. 1r0 end. > > >> > > >> : > > >> > > >> m|x*m mi y > > >> > > >> ) > > >> > > >> 17 mi 6 > > >> > > >> 3 > > >> > > >> NB. Mike Day's Table > > >> > > >> 2 3 4 (17 mi)table >:i.8 > > >> > > >> +-+---------------------+ > > >> > > >> | |1 2 3 4 5 6 7 8| > > >> > > >> +-+---------------------+ > > >> > > >> |2|2 1 12 9 14 6 10 13| > > >> > > >> |3|3 10 1 5 4 9 15 11| > > >> > > >> |4|4 2 7 1 11 12 3 9| > > >> > > >> +-+---------------------+ > > >> > > >> > > >> I have some questions regarding system solving modulo m that I will > > offer > > >> in a new thread in a few days. > > >> > > >> Best, Cliff > > >> > > >> On Thu, Mar 30, 2023 at 12:11 PM Clifford Reiter< > [email protected]> > > >> wrote: > > >> > > >>> I think I recall a conversation, some decades ago, with Roger about > > >>> whether specifying a modulus for system solving makes sense for J. I > > >>> thought maybe that was a use for the fit conjunction but now think > that > > >>> would be a poor choice for such a numeric function. I have vague > > memories > > >>> of J essays on guass-jordan row reduction and extended gcds but > didn't > > find > > >>> them poking around J help. > > >>> They could be useful for what I had in mind and modular inverses > would > > be > > >>> part of that. Perhaps someone has those handy and could offer an > > addon? New > > >>> adverbs giving b m %.: a and m %.: a anyone? > > >>> Best, Cliff > > >>> > > >>> On Wed, Mar 29, 2023 at 5:02 PM 'Michael Day' via Programming < > > >>> [email protected]> wrote: > > >>> > > >>>> While this primitve works nicely in an example: > > >>>> > > >>>> (2 3 4) (17&|@*)/ table >:i.8 > > >>>> +-------+---------------------+ > > >>>> |17&|@*/|1 2 3 4 5 6 7 8| > > >>>> +-------+---------------------+ > > >>>> |2 |2 4 6 8 10 12 14 16| > > >>>> |3 |3 6 9 12 15 1 4 7| > > >>>> |4 |4 8 12 16 3 7 11 15| > > >>>> +-------+---------------------+ > > >>>> > > >>>> I find this less satisfying: > > >>>> (2 3 4) (17&|@%)/ table >:i.8 > > >>>> +-------+-----------------------------------------------+ > > >>>> |17&|@%/|1 2 3 4 5 6 7 8| > > >>>> +-------+-----------------------------------------------+ > > >>>> |2 |2 1 0.666667 0.5 0.4 0.333333 0.285714 0.25| > > >>>> |3 |3 1.5 1 0.75 0.6 0.5 0.428571 0.375| > > >>>> |4 |4 2 1.33333 1 0.8 0.666667 0.571429 0.5| > > >>>> +-------+-----------------------------------------------+ > > >>>> > > >>>> I have a function which does what one would expect. I'll rename it > as > > >>>> m17div here, details unimportant for this discussion: > > >>>> (2 3 4) m17div/ table >:i.8 > > >>>> +-------+---------------------+ > > >>>> |m17div/|1 2 3 4 5 6 7 8| > > >>>> +-------+---------------------+ > > >>>> |2 |2 1 12 9 14 6 10 13| > > >>>> |3 |3 10 1 5 4 9 15 11| > > >>>> |4 |4 2 7 1 11 12 3 9| > > >>>> +-------+---------------------+ > > >>>> ( eg 3 % 2 == 10 mod 17 because 3 = 17 | 2 * 10 ) > > >>>> > > >>>> Would anyone else find this return of integer results useful or is > it > > >>>> better > > >>>> to force a floating output? > > >>>> > > >>>> (Henry tells me that m&|@^ returns integer results, working ok when > > m^2 > > >>>> can be represented as a non-extended integer.) > > >>>> > > >>>> Thanks, > > >>>> > > >>>> Mike > > >>>> > > >>>> > ---------------------------------------------------------------------- > > >>>> For information about J forums seehttp:// > www.jsoftware.com/forums.htm > > >>>> > > >> ---------------------------------------------------------------------- > > >> For information about J forums seehttp://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- > > > For information about J forums seehttp://www.jsoftware.com/forums.htm > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
