NB. Expressions used in "Prime Factorization in the Gaussian integers"
NB. by Cliff Reiter, Math Dept, Lafayette College, Easton, PA, U.S.A.
NB. Submitted to Journal of J, June 2013

NB. Arithmetic in Gaussian integers

+ 3j4

3j4*+3j4

N=: *+

N 3j4

3j4 + 2j3

0j1 * 0j1

0j1 * 1j2

3j4 * 1j2

3j4 % 1j2

NB. gcd of gaussian integer
*/1j1 3j_4 5j12

*/1j1 1j_1

2 +. 47j79

NB. units
N 1 0j1 _1 0j_1

3j4 * 1 0j1 _1 0j_1

NB. Implementation
NB. -1 is a Quadratic residue witness

qrw=: 3 : 0
p=.x: y
e=.(p-1)%2 4
y=.0
while. y~:p-1 do.
  n=.x: ?&.<:p
  'y x'=.p&|@:(n&^)e
end.
x
)

qrw 101

NB. split p cong to 1 mod 4
splitm1=: (,0j1*+)@(+. qrw j. 1:)"0

splitm1 13

NB. example
y=. _13090j_8806

]pn=.q: N y

'p1 p2 p3'=.}.&.>(4&| </. ]) 1 2 3,pn

p1

p2

p3

]pf=.(#p2)#1j1

]pf=.pf,;<@(-:@#{.])/.~p3

]sp1=.,splitm1 ~.p1

]y=.y%*/pf

NB. integer query
iq=: =<.

iq 3 3.1

NB. Gaussian integer query
giq=:*./@:iq@:(**|)@:+."0

giq 3j4 3.1j4

NB. gaussian integer fuzz removal
giclean=:(**|)&.+.

giclean 3j1e_16

NB. main factorization function
gifactor=:3 : 0
pn=.q: N y
'p1 p2 p3'=.}.&.>(4&| </. ]) 1 2 3,pn
pf=.(#p2)#1j1
pf=.pf,;<@(-:@#{.])/.~p3
sp1=.,splitm1 ~.p1
y=.giclean y%*/pf
for_sp. sp1 do.
   while. giq q=.y%sp do.
   y=.giclean q
   pf=.pf,sp
   end.
end.
y,(/:|)pf
)

gifactor _13090j_8806

NB. gaussian prime query
giprimeq=:2 = #@gifactor

NB. gaussian integer prime query extended to 0
gipq=:0:`giprimeq@.(0&~:)"0

gipq 0 1 2 3 4 5 1j4

j./~i:5

gipq j./~i:5

load 'viewmat'

NB. views of some primes
viewmat -.gipq j./~i:10

viewmat -.gipq j./~i:40