In case anyone is interested, I wrote a verb to calculate the Jacobi symbol for
positive integers n,m (n/m), although my J syntax is pretty awkward:
NB. Jacobi symbol (x/y)
NB. x is numerator (positive int, or zero)
NB. y is denominator (positive int)
jac=: 4 : 0
numer=. x
denom=. y
jacobi=. 1
if. numer = 0 do.
0
return.
end.
if. numer < 0 do.
numer=. numer * _1
end.
while. 0 < numer do.
while. 0 = 2 | numer do.
numer=. numer % 2
if. 3 5 e.~ 8 | denom do.
jacobi=. jacobi * _1
end.
end.
if. numer = 1 do.
jacobi
return.
end.
if. 3 3 -: 4 | numer , denom do.
jacobi=. jacobi * _1
end.
tempy=. numer | denom
denom=. numer
numer=. tempy
end.
jacobi
)
e.g. find the x values that give jacobi symbol of 1, when y = 23, and x is in
{0, ..., 22}
>:I.-:>:}. (i. 23) jac"(0 0) 23 NB. get rid of zero)
1 2 3 4 6 8 9 12 13 16 18
The jacobi symbol's meaning is weaker than I remembered. If it gives 1, that
doesn't necessarily mean that x is a quadratic residue of y (unless y is
prime).
e.g.
(i.16) jac"(0 0) 16
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
because (a/16) = (a/2)*(a/2)*(a/2)*(a/2), so any -1's cancel each other out.
--------------------------------------------
On Tue, 1/5/16, 'Pascal Jasmin' via Programming <[email protected]>
wrote:
Subject: Re: [Jprogramming] Prime-based selection oddity
To: "[email protected]" <[email protected]>
Date: Tuesday, January 5, 2016, 12:24 PM
Also,
all odd numbers mod 16 are 1 3 5 7 9 11 13 15,
and squared have 1 of 2 results.
#/.~ 16 | *: 3 + 2 *
i.2000
1000 1000
similarly to odd numbers mod
10 squared are 1 and 9 and 5.
Its a bit interesting that there are slightly
more 9s than 1s and it increases somewhat irregularly in
each range.
#/.~ 16 | *: p: >: i.1000
506 494
#/.~ 16 | *: p: >: i.2000
1005 995
#/.~ 16 | *: p: >:
i.3000
1508 1492
#/.~ 16
| *: p: >: i.4000
2018 1982
#/.~ 16 | *: p: >: i.5000
2522 2478
----- Original Message -----
From: Devon McCormick <[email protected]>
To: J-programming forum <[email protected]>
Sent: Monday, January 4, 2016 9:13 PM
Subject: [Jprogramming] Prime-based selection
oddity
Recently I was
looking at how I might generate something that look like
an
encryption key and noticed this
oddity:
#val=.
'0123456789ABCDEF'
16
val{~(#val)|2^~p:i.128
49919919191919199991119119199119199199199911919199111911919199911991991119919911991119119191199191999991919111191911919991999991
frtab
val{~(#val)|2^~p:i.128
+--+-+
|1 |4|
+--+-+
|68|9|
+--+-+
|59|1|
+--+-+
Where "frtab" is a
frequency table generator:
frtab=: 3 : 0
cts=. #&>y</.y
NB. # unique items...
if.
-.isNum y do. NB. Special case enclosed,
text mat, text vec,
if.
(L.=0:) y do. (<"0 cts),.<"0 ~.y else.
if. 2=#$y do.
(<"0 cts),.<"1 ~.y else. (<"0
cts),.<"0 ~.y end.
end.
else.
cts,.~.y end. NB. and simple numeric vec.
NB.EG (1 2 3 2 1,. 11 22 33 222 99) -: frtab 11
22 22 33 33 33 222 222 99
)
Any obvious reason why the 16|
of squares of primes should return only "1"
and "9" for this sample?
--
Devon McCormick, CFA
Quantitative Consultant
----------------------------------------------------------------------
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
