Re: A question

From: Tom St Denis (tomstdenis@yahoo.com)
Date: 04/19/03 

From: tomstdenis@yahoo.com (Tom St Denis)
Date: 19 Apr 2003 09:49:12 -0700

"Phil Carmody" <thefatphil_demunge@yahoo.co.uk> wrote in message news:<pan.2003.04.19.14.52.04.250969@yahoo.co.uk>...
> On Fri, 18 Apr 2003 15:54:34 +0000, contact wrote:
>
> > Does anyone know of an algorithm that can indicate if a perfect square root
> > of an integer exists without having to slog thru all the code to actually
> > find the square root? I've done some searching on google and in Schneier's
> > book of AC but can't find anything.
>
> Check to see if it's a quadratic residue modulo a bunch of small primes.
> Include a power of 2 as the first check, as that can reject a fair
> proportion of numbers fairly quickly.

Um, this isn't true as two cannot be used at all. Consider 9 mod 2
and 16 mod 2.

In fact since the field Z/2Z only has one unit there are no quadratic
non-residues to test against.

Tom

Relevant Pages

  • Re: A question
    ... > Does anyone know of an algorithm that can indicate if a perfect square root ... > of an integer exists without having to slog thru all the code to actually ...
    (sci.crypt)
  • Re: A question
    ... > of an integer exists without having to slog thru all the code to actually ... > find the square root? ... I've done some searching on google and in Schneier's ...
    (sci.crypt)
  • A question
    ... Does anyone know of an algorithm that can indicate if a perfect square root ... of an integer exists without having to slog thru all the code to actually ... Bill Johnson ... "Avoid having your ego so close to your position that when your position ...
    (sci.crypt)
Quantcast