Actually, thinking about this, the relevant part of that extended
euclidean verb could be expressed more concisely:
eu=: 0 { (] ,: [ - <.@%&{. * ])/^:(*@{.@{:)^:_@,.&0 1x@,
11 eu 3
1 4
This allows us to define invmod as:
invmod=: [ ((1 = {.@]) * {:@] + [ * 0 >: {:@]) eu
11 invmod 3
4
Thanks,
--
Raul
On Sun, Feb 2, 2014 at 7:22 PM, Raul Miller <rauldmil...@gmail.com> wrote:
> Here's an alternative to imw (an implementation of the extended
> euclidean algorithm):
>
> eeu=: [: , (] ,: (1 1 1 0*[) - <.@%&{. * (1 1 1
> 0^~]))/^:(*@{.@{:)^:_@(,.&(x:=0 1 0))
>
> Example use:
>
> eeu 11 3
> 1 _1 4 _1 0 3 _11 _2
>
> Note, however, that the result is structured differently:
>
> The result of (4 { imw^:_ ] ,~ 1 0 0 1x) is 0 { eeu
>
> (But the result of (2 { imw^:_ ] ,~ 1 0 0 1x) is 2 { eeu)
>
> I'm still playing around with these ideas, and trying to digest them,
> and the performance of this approach isn't really all that different.
> But I sort of like the way this expression looks.
>
> Thanks,
>
> --
> Raul
>
> On Wed, Jan 29, 2014 at 3:02 PM, Pascal Jasmin <godspiral2...@yahoo.ca> wrote:
>> Here is the first invmod method
>>
>> invmod=: 4 : 0
>> NB. inverse of y mod x (x|y)
>> NB. uc vc ud vd d c where d c init as x y
>> NB. q =. d<.@%c -- (4&{ <.@%~ {:)
>>
>> a=. imw^:_ ] 1x,0x,0x,1x,x,y
>> if. 1~: 4{a do. 0 return. end.
>> if.0< 2{ a do. 2{ a else. x+2{a end.
>>
>> )
>> imw =: ((2&{ - {. * 4&{ <.@% {:),(3&{ - 1&{ * 4&{ <.@% {:), 2&{., ({: | 4&{)
>> ,~{:)^:(0 ~: {:)
>> testinvmod =: (0 1 e.~ [ | ]* invmod)
>>
>> 11 invmod 3
>> 4
>>
>> (14114588 +i.10) ( invmod)"0 1 ] 3x
>> 4704863 0 9409727 4704864 0 9409729 4704865 0 9409731 4704866
>>
>> ts '(14114588x +i.10000) (testinvmod )"0 ] 3x'
>> 2.74558/sec 3.14547MB
>> ts '(14114588 +i.10000) (invmod )"0 ] 3'
>> 2.96905/sec 3.26822MB
>>
>>
>> ----- Original Message -----
>> From: Pascal Jasmin <godspiral2...@yahoo.ca>
>> To: "programm...@jsoftware.com" <programm...@jsoftware.com>
>> Cc:
>> Sent: Wednesday, January 29, 2014 11:35:19 AM
>> Subject: [Jprogramming] math requests
>>
>>
>>
>> With all of the mathematicians on this list, these functions have likely
>> been implemented before in J.
>>
>> elyptic curve point add, multiplication and double
>> a python reference implementation:
>> https://github.com/warner/python-ecdsa/blob/master/ecdsa/ellipticcurve.py
>>
>> the functions are: __add__ __mul__ and double
>>
>> if I may suggest J explicit signatures for the first 2 functions as:
>>
>> F =: 4 : 0
>> 'yx yy yo' =. y
>> 'xx xy xo' =. x
>> )
>>
>> Some other methods than the python reference could be considered here:
>>
>> http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
>>
>>
>> also appreciated if you have in implementation of inverse_mod
>> for reference function of same nate at:
>> https://github.com/warner/python-ecdsa/blob/master/ecdsa/numbertheory.py
>>
>> ----------------------------------------------------------------------
>> 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
