Hi Wei, I'm trying to study the distribution of perfect squares over various residues. Most factoring algorithms look at quadratic residues. I've noticed that other powers (cubics, x^5) will also yield perfect squares as residues. Some powers (such as x^5), yield a perfect square sooner than others (for example, x^2 when n is of a certain form).
What I would like to answer is: if x^y mod n = perfect sqaure, then * what should one choose as y * or fix y. Then near what x should one look for a perfect square. Jeff >>> [EMAIL PROTECTED] 10/24/2005 1:27 AM >>> That looks fine, or you can extend the idea further by checking quadratic residuosity modulo a number of small integers. See http://www.gnu.org/software/gmp/manual/html_node/Perfect-Square-Algorithm.html. Why do you need to do lots of IsSquare() tests, I'm curious? ----- Original Message ----- From: "Jeffrey Walton" <[EMAIL PROTECTED]> To: <[email protected]> Sent: Thursday, October 20, 2005 1:06 PM Subject: IsSquare( ) > Hi All, > > I was wondering if the following would be an improvement for testing if a > number is a square (from Integer.cpp). It is a quick and dirty test. I ask > because I want to perform a lot if tests using IsSquare() on quadrtic > residues. > > bool Integer::IsSquare() const > { > Integer r; > word digit = 0; > > if( false == IsNegative( ) ) { > Integer::Divide(digit, r, *this, 10); > > //\ Perfect squares end in the following > if( digit != 0 && digit != 1 && digit != 4 && > digit != 5 && digit != 6 && digit != 9 ) { return false; } > } > > r = SquareRoot(); > return *this == r.Squared(); > } > >
