20201016, 19:44  #1 
Mar 2016
101000101_{2} 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
1356_{10} 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
1360_{10} 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^{6}·71 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 