20201016, 19:44  #1 
Mar 2016
5×71 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 (pn, 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 20201016 at 19:45 
20201017, 02:44  #2 
Aug 2002
Buenos Aires, Argentina
10101100100_{2} 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; } 
20201017, 05:11  #3 
"Mihai Preda"
Apr 2015
1,373 Posts 
Apparently the complexity of jocobi symbol is the same as the GCD. For 100Mbits residues, GnuMP takes about 30s on CPU. (which is abouth the same time as a GCD).

20201017, 13:37  #4  
Feb 2017
Nowhere
2×47×53 Posts 
Quote:
The following pertains to the specific case at hand. Apart from the individual factors, we have kronecker(n,2*n^2  1) = 1, if 4n; 1, if n == 1 (mod 4); 1, if n == 2 (mod 4); and 1, if n == 3 (mod 4). Also, kronecker(pn,p) = kronecker(n,p) if p == 3 (mod 4); and kronecker(pn,p) = kronecker(n,p) if p == 1 (mod 4). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Quadratic residue counts related to four squares representation counts  Till  Analysis & Analytic Number Theory  8  20201011 18:11 
a quadratic residue modulo and( Mersenne numbre)  baih  Miscellaneous Math  6  20200928 15:48 
Quadratic residue mod 2^p1  alpertron  Miscellaneous Math  17  20120430 15:28 
Predicting QS and NFS runtime  jasonp  Factoring  2  20110307 01:22 
ECM Runtime and F20  D. B. Staple  Factoring  11  20071212 16:52 