mersenneforum.org > Math runtime for the calculation of a quadratic residue
 Register FAQ Search Today's Posts Mark Forums Read

 2020-10-16, 19:44 #1 bhelmes     Mar 2016 52·13 Posts runtime for the calculation of a quadratic residue A peaceful and pleasant day for you, What is the runtime of the jacobi / legendre / kronecker function in order to determine wether x is a quadratic residue concerning the prime p. Is this function faster than fast exponentation ? I would like to calculate the function f(n)=2n²-1 for increasing n to split the function term in primes and to determine jacobi (n, p) and jacobi (p-n, p) Perhaps someone can give me a hint, Greetings from Euler, I think he was the first person who occupies with quadrac reciprocity. Bernhard Last fiddled with by bhelmes on 2020-10-16 at 19:45
 2020-10-17, 02:44 #2 alpertron     Aug 2002 Buenos Aires, Argentina 135610 Posts Computing the Jacobi symbol is a lot faster than modular exponentiation. This is the source code I wrote in C language based on Crandall's and Pomerance's Prime Number book: Code: // Calculate Jacobi symbol by following algorithm 2.3.5 of C&P book. int JacobiSymbol(int upper, int lower) { int a = upper % lower; int m = lower; int t = 1; while (a != 0) { int tmp; while ((a & 1) == 0) { // a is even. a >>= 1; if ((m & 7) == 3 || (m & 7) == 5) { // m = 3 or m = 5 (mod 8) t = -t; } } tmp = a; a = m; m = tmp; // Exchange a and m. if ((a & m & 3) == 3) { // a = 3 and m = 3 (mod 4) t = -t; } a = a % m; } if (m == 1 || m == -1) { return t; } return 0; }
2020-10-17, 05:11   #3
preda

"Mihai Preda"
Apr 2015

24·5·17 Posts

Quote:
 Originally Posted by bhelmes What is the runtime of the jacobi / legendre / kronecker function in order to determine wether x is a quadratic residue concerning the prime p.
Apparently the complexity of jocobi symbol is the same as the GCD. For 100M-bits residues, Gnu-MP takes about 30s on CPU. (which is abouth the same time as a GCD).

2020-10-17, 13:37   #4
Dr Sardonicus

Feb 2017
Nowhere

32·5·101 Posts

Quote:
 Originally Posted by bhelmes I would like to calculate the function f(n)=2n²-1 for increasing n to split the function term in primes and to determine jacobi (n, p) and jacobi (p-n, p)
The overall result about the computation has already been posted. It's comparable to a gcd computation.

The following pertains to the specific case at hand.

Apart from the individual factors, we have

kronecker(n,2*n^2 - 1) =
1, if 4|n;
1, if n == 1 (mod 4);
1, if n == 2 (mod 4); and
-1, if n == 3 (mod 4).

Also,

kronecker(p-n,p) = -kronecker(n,p) if p == 3 (mod 4); and
kronecker(p-n,p) = kronecker(n,p) if p == 1 (mod 4).

 Similar Threads Thread Thread Starter Forum Replies Last Post Till Analysis & Analytic Number Theory 8 2020-10-11 18:11 baih Miscellaneous Math 6 2020-09-28 15:48 alpertron Miscellaneous Math 17 2012-04-30 15:28 jasonp Factoring 2 2011-03-07 01:22 D. B. Staple Factoring 11 2007-12-12 16:52

All times are UTC. The time now is 11:32.

Sun May 16 11:32:15 UTC 2021 up 38 days, 6:13, 0 users, load averages: 1.20, 1.48, 1.53