Big Oh of LL test?

jbohanon · 2002-09-09, 02:48

Just curious to find out.

The new primality test postulates that they can get it down to a cubic polynomial and I'm curious if that might beat out the LL-primality test.

Prime95 · 2002-09-09, 21:18

O(n^2 log n)

where n is the number of bits in the Mersenne number.

jbohanon · 2002-09-09, 23:59

You mean the bits of p or 2^p-1?

Prime95 · 2002-09-10, 01:11

Bits of 2^p-1. In other words, O(p^2 log p)

2002-09-09, 02:48	#1
jbohanon Sep 2002 3₈ Posts	Big Oh of LL test? Just curious to find out. The new primality test postulates that they can get it down to a cubic polynomial and I'm curious if that might beat out the LL-primality test.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing	Trilo	Miscellaneous Math	25	2018-03-11 23:20
New PC test re-test plan?	dh1	Information & Answers	8	2015-12-11 11:50
Double check LL test faster than first run test	lidocorc	Software	3	2008-12-03 15:12
Will the torture test, test ALL available memory?	swinster	Software	2	2007-12-01 17:54
A primality test for Fermat numbers faster than Pépin's test ?	T.Rex	Math	0	2004-10-26 21:37

2002-09-09, 21:18	#2
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 2×53×71 Posts	O(n^2 log n) where n is the number of bits in the Mersenne number.

2002-09-09, 23:59	#3
jbohanon Sep 2002 3 Posts	You mean the bits of p or 2^p-1?

2002-09-10, 01:11	#4
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 2×53×71 Posts	Bits of 2^p-1. In other words, O(p^2 log p)