mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-10-16, 19:44   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

7·41 Posts
Default 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
bhelmes is offline   Reply With Quote
Old 2020-10-17, 02:44   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101001101012 Posts
Default

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;
}
alpertron is offline   Reply With Quote
Old 2020-10-17, 05:11   #3
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

24×83 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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).
preda is offline   Reply With Quote
Old 2020-10-17, 13:37   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

378410 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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).
Dr Sardonicus is offline   Reply With Quote
Reply

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 2020-10-11 18:11
a quadratic residue modulo and( Mersenne numbre) baih Miscellaneous Math 6 2020-09-28 15:48
Quadratic residue mod 2^p-1 alpertron Miscellaneous Math 17 2012-04-30 15:28
Predicting QS and NFS runtime jasonp Factoring 2 2011-03-07 01:22
ECM Runtime and F20 D. B. Staple Factoring 11 2007-12-12 16:52

All times are UTC. The time now is 09:09.

Wed Nov 25 09:09:50 UTC 2020 up 76 days, 6:20, 4 users, load averages: 2.47, 1.62, 1.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.