here is code for rsa signing that uses CRT. Its not J-pretty because you/I
want to precalculate each of the CRT params. invmod is especially expensive.
nbSign =: 4 : 0
'pub priv' =. x
'pE N' =. pub
'd p q dp dq qi' =. priv
e=. N |s256 bighash ^:(2=3!:0) (3!:1)^:((0< L.) +. 1 < #) y
e1=. dp p&|@^~ e
e2=. dq q&|@^~ e
h =. p| qi * e1+ p - e2
y; N | e2+ h*q
)
pub and priv keys are passed as boxed x.
y is message to sign which gets converted (if needed) into a byte array e
code uses J special code optimized version of modexp.
returns message ; signature
priv key components are
d =. m invmod~ p *&<: q
dp =. (<:p) | d
dq =. (<:q) | d
qi =. p invmod q
imw=: ((2&{ - {. * 4&{ <.@% {:),(3&{ - 1&{ * 4&{ <.@% {:), 2&{., ({: | 4&{)
,~{:)^:(0 ~: {:)
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
a=. imw^:_ ] 1x,0x,0x,1x,x,y
if. 1~: 4{a do. 0 return. end. NB. returns 0 if no inverse
if.0< 2{ a do. 2{ a else. x+2{a end.
)
----- Original Message -----
From: Dan Bron <[email protected]>
To: [email protected]
Cc:
Sent: Thursday, April 17, 2014 12:22:29 PM
Subject: [Jprogramming] Chinese remainder thereom
I sporadically scan the list of open tasks for J on RosettaCode:
http://rosettacode.org/wiki/Reports:Tasks_not_implemented_in_J
Most of these tasks lack a J solution for a good reason (e.g. stream
processing, low-level IO, heavy-duty GUI, multithreading, or just too many
tuits). But some fit nicely into J's domain, and simply need someone to
post a solution.
Chinese remainder thereom is an example of the latter:
http://rosettacode.org/wiki/Chinese_remainder_theorem
The algorithm looks pretty straightforward to me, and indeed I could
brute-force it by writing an explicit verb which matches, loop-for-loop,
the Python solution (for example).
But instead, I'd like to show off J's native grace and elegance;
unfortunately, it's been a long while since my undergraduate math days,
and I don't think I have the algebraic chops to tackle this problem
elegantly. Though I do have enough of a native instinct left to suspect
that there's room for a very pretty solution taking advantage of some of
J's more distinctive primitives (in particular +. #: %. seem relevant).
So, what's the most elegant way you could implement the Chinese remainder
theorem in J?
-Dan
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
