Oh, I didn't know about legendre.ijs. Thanks.
I don't think there is much use for it in the addons, but I don't see any
reason not to have it.
Anyway, I cleaned it up slightly and added a few tests, because I was a little
sceptical it covers all cases correctly:
NB. Jacobi symbol (x/y)
NB.
NB. x is an integer and y is a positive integer.
jac=: 4 : 0
numer=. x
denom=. y
jacobi=. 1
if. numer = 0 do.
0
return.
elseif. 1 < numer +. denom do.
0
return.
end.
if. numer < 0 do.
numer=. -numer
if. 3 = 4 | denom do.
jacobi = -jacobi
end.
end.
while. 0 < numer do.
while. 0 = 2 | numer do.
numer=. numer % 2
if. 3 5 e.~ 8 | denom do.
jacobi=. -jacobi
end.
end.
if. numer = 1 do.
jacobi
return.
end.
if. 3 3 -: 4 | numer , denom do.
jacobi=. -jacobi
end.
tempy=. numer | denom
denom=. numer
numer=. tempy
end.
jacobi
)
NB. tests
NB. get quadratic residues of y
qres =: /:~@:~.@:(| *:@:>:@:i.@:<:)
NB. get the elemnts of {0,..., y-1} with jacobi symbol = 1
NB. These are not necessarily all quadratic residues.
NB. if y is prime then the returned elements are quadratic residues.
jacobires =: [: >: I.@:(1&=)@:(>:@:i.@:<: jac"0 0 ]) { i.
NB. test primes
(qres 5) -: (jacobires 5)
(qres 11) -: (jacobires 11)
(qres 79) -: (jacobires 79)
(qres 557) -: (jacobires 557)
(qres 7927) -: (jacobires 7927)
NB. test composites
( 1 2 4 8) -:(jacobires 15)
(1 2 4 5 7 8) -: (jacobires 9)
(1 4 5 16 17 20) -: jacobires 21
--------------------------------------------
On Wed, 1/6/16, chris burke <[email protected]> wrote:
Subject: Re: [Jprogramming] Prime-based selection oddity
To: "Programming forum" <[email protected]>
Date: Wednesday, January 6, 2016, 12:00 AM
Thanks. We already have
script ~addons/math/misc/legendre.ijs. Should this
be added to that directory?
On 5 January 2016 at 02:50, 'Jon Hough'
via Programming <
[email protected]>
wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
