View Single Post
Old 2009-10-11, 12:44   #6
akruppa's Avatar
Aug 2002

2,467 Posts

P+1 can either end up working in a group of order p-1 or p+1, depending on whether x02 - 4 is a quadratic residue modulo p or not. Since we don't know p in advance, we can't tell which one it was until after p was found. If it was actually p-1, the GMP-ECM prints the message you quoted. The effect of getting either p-1 or p+1 is pretty fundamental to how P+1 works, we don't know how to construct a quadratic extension of GF(p) reliably without knowing p. The extra exponentiation etc. we do in GMP-ECM is not related to this.

akruppa is offline   Reply With Quote