Re: Naive Square root algorithm for GNFS ?

From: Michael Amling (nospam_at_nospam.com)
Date: 03/30/05 

Date: Wed, 30 Mar 2005 01:16:40 GMT

Jean-Luc Cooke wrote:
> Tom St Denis <tomstdenis@gmail.com> wrote:
>
>
>>Jean-Luc Cooke wrote:
>>
>>>Not specific to NFS:
>>>
>>>int sqrtmod(int x, int m) {
>>> int r;
>>>
>>> // just in case...
>>> x %= m;
>>>
>>> for (r=1; r<m; m++) {
>
>
>>Technically this is upto (m-1)/2 and it's "r++" not m.
>
>
> "No" and "doh!" ... that is assuming this is what he wants.
>
> Exmaple:
> 4 = (3*3) % 5
> 1 = (4*4) % 5

   What is this an example of? Your sqrtmod(4,5) returns 2 and
sqrtmod(1, 5) returns 1.
   I think you mean "doh!" and "doh!". If x has no square root modulo m
in 1..(m-1)/2 then x has no square root in (m+1)/2..m-1 modulo m.

--Mike Amling