30 lines
540 B
Plaintext
30 lines
540 B
Plaintext
leg=: dyad define
|
|
x (y&|)@^ (y-1)%2
|
|
)
|
|
|
|
tosh=:dyad define
|
|
assert. 1=1 p: y [ 'y must be prime'
|
|
assert. 1=x leg y [ 'x must be square mod y'
|
|
pow=. y&|@^
|
|
if. 1=m=. {.1 q: y-1 do.
|
|
r=. x pow (y+1)%4
|
|
else.
|
|
z=. 1x while. 1>: z leg y do. z=.z+1 end.
|
|
c=. z pow q=. (y-1)%2^m
|
|
r=. x pow (q+1)%2
|
|
t=. x pow q
|
|
while. t~:1 do.
|
|
n=. t
|
|
i=. 0
|
|
whilst. 1~:n do.
|
|
n=. n pow 2
|
|
i=. i+1
|
|
end.
|
|
r=. y|r*b=. c pow 2^m-i+1
|
|
m=. i
|
|
t=. y|t*c=. b pow 2
|
|
end.
|
|
end.
|
|
y|(,-)r
|
|
)
|