Re: Naive Square root algorithm for GNFS ?

From: Jean-Luc Cooke (jlcooke_at_engsoc.org)
Date: 03/29/05 

Date: 29 Mar 2005 19:06:47 GMT

Not specific to NFS:

int sqrtmod(int x, int m) {
  int r;

  // just in case...
  x %= m;

  for (r=1; r<m; m++) {
    if ( ((r*r) % m) == x )
      return r;
  }

  return 0;
}

That what you're looking for?
Just a simple "find r such that r*r == x (mod m)"?

JLC

Per Leslie Jensen <pleslie@diku.dk> wrote:
> I am currently writing my master thesis in computer science and one of the
> things I am trying to do is to make a c++ framework for the GNFS algorithm
> and for illustration I have implemented the algorithm, but I am having
> difficulty with the square root part of the algorithm, I have not put any
> restrictions to input so Couveignes method won't do, and Peter Montgomerys
> method is far to complicated for illustration purposes...

> So my question is: are there any ultra-naive method for extracting the
> square-roots ? The purpose is not to make the fastest version but making
> the algorithm more widely available so more implementation work can be
> done by computerscientists without a M.Sc. in mathematics...

> I simply need the most simple method for the square root part...

> Thanks in advance
> Per Leslie Jensen

> --
> ####################################################
> * Per Leslie Jensen <pleslie@diku.dk>
> * Graduate Student at the university of Copenhagen
> * -- Department of Computer Science
> *
> #################################################### 

--