Re: Naive Square root algorithm for GNFS ?

From: Unruh (unruh-spam_at_physics.ubc.ca)
Date: 03/29/05 

Date: 29 Mar 2005 19:47:14 GMT

Jean-Luc Cooke <jlcooke@engsoc.org> writes:

>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)"?

A bit slow wouldn;t you say? Of course he mentioned nothing about speed (or
rather he did say speed did not matter) so your's is fine.
I think you also need a trap in case no square root exists.

>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
>> *
>> ####################################################

>--