Re: issquare() for t_INTMOD's

[Alan McConnell <alan@patriot.net>]

On Sat, Oct 22, 2011 at 12:23:12AM +0200, Bill Allombert wrote:
> On Thu, Oct 20, 2011 at 07:32:55PM -0400, Alan McConnell wrote:
> 
> >   	 Bill, and other pari-developers: can some serious work be
> > 	 done on this issue?   A lot of us mathematicians(and IT
> > 	 crackers) really need for factor(p) to be as fast as
> > 	 isprime(p).   Surely some polishing of the algorithms could
> > 	 make this possible???   Please Really Hasten!
> 
> I am afraid this is not that easy. Basically there are two classes of
> algorithms:
> 1) algorithms that can prove that a number is composite.
> 2) algorithms that can prove that a number is prime.
     	<LOL>  For sure.  Since Diffie-Hellman, many(most?) public
	key encryption algorithms have depended on the fact that
	it is (comparatively) easy to prove that a number is prime,
	but finding the factors of a (presumably) composite number
	is orders of magnitude harder.  So my message was basically
	to urge you, and everyone, to work hard to even up the
	difficulties.  This would probably destroy public key
	cryptography, but math is more important than commerce<g>.

	I emphasized "Really Hasten" and "Really Hopeful", in the
	hope that people would look at the initial letters.  For
	if one had full understanding of the zeros of the Riemann
	Zeta function, it is my understanding that factoring would
	be a cinch(maybe I'm wrong here, I'm not an expert)

Please forgive the jokiness!  We return you now to your regular
programming.

Alan

-- 
Alan McConnell :  http://patriot.net/users/alan
     Have the courage to be ignorant of a great number of things, in 
     order to avoid the calamity of being ignorant of every thing.