View Single Post
Old 2020-06-15, 21:00   #5
Batalov's Avatar
Mar 2008

23E016 Posts

Originally Posted by jshort View Post
Fyi - I personally used the Pollard-rho algorithm with the iterating function x_{n+1} = x_{n}^{24 \cdot (2k+1)} + 1 to weed out many composites

Alternatively, the p-1 test could be used instead to weed out composites. I'm not sure which of the two would be more efficient tbh (if anyone knows the answer to this, that'd be awesome!).
In additional to what UTM's (and Mathworld's iirc has one) comprehensive pages says, quick note: Gaussian Mersenne norms share many similarities to Mersenne numbers. In particular,
* n needs to be prime - why? because otherwise there is an algebraic factorization. (And in the algebraic factorization you will find both + and - forms)
* Any factor (except 5 which is intrinsic) is of form 2 * k * p + 1, so trial factoring is simplified but is very similar to Mersenne project: you don't sieve database-wide - you pre-factor each candidate. Furthermore, just like factors of Mersenne composites, these will not share the same factors (except the trivial case when one divides the other).

...that's just a few quick thoughts is a spare time during lunch break.

P.S. All primes of this form at this time are known -- loosely speaking to the limit of p < 10,000,000. So searching below this limit will not bring too much joy to the searcher.
Batalov is offline   Reply With Quote