Prime Benchmarks

[sethtroisi]

I was trying to understand which of the many is_X_prp to use and I benchmarked all the prp functions in colab. I'm not sure if this is helpful for other people but it was interesting for me, if it would be useful to record in some place I'm happy to write it up in any format.

For strong composite numbers (no factors < 10,000)

bits	is_strong_prp	is_euler_prp	is_fermat_prp	is_fibonacci_prp	is_lucas_prp	is_strong_lucas_prp	is_extra_strong_lucas_prp	is_selfridge_prp	is_strong_selfridge_prp	is_bpsw_prp	is_strong_bpsw_prp	is_prime
100	1.00	1.32	1.00	5.13	15.79	9.57	9.70	9.98	9.45	1.32	0.97	1.44
150	1.00	1.03	1.01	5.94	12.23	10.64	10.73	23.56	12.86	1.08	1.13	1.23
200	1.00	1.31	0.96	3.54	7.40	7.88	8.61	7.91	6.89	0.96	0.96	1.05
300	1.00	0.81	0.72	2.42	4.78	6.05	7.01	5.89	3.24	0.67	0.67	0.70
400	1.00	0.99	1.07	2.41	4.29	4.27	4.03	3.94	4.07	0.97	1.01	1.04
500	1.00	1.18	1.12	2.25	4.29	4.42	4.24	3.99	3.89	1.08	1.09	1.07
750	1.00	1.04	1.03	2.09	4.25	4.18	4.23	3.99	3.95	0.96	0.96	0.98
1000	1.00	0.95	1.02	2.12	4.31	4.28	4.25	4.04	4.02	0.98	0.95	0.97
avg	1.00	1.08	0.99	3.24	7.17	6.41	6.60	7.91	6.05	1.00	0.97	1.06

For prime numbers

bits	is_strong_prp	is_euler_prp	is_fermat_prp	is_fibonacci_prp	is_lucas_prp	is_strong_lucas_prp	is_extra_strong_lucas_prp	is_selfridge_prp	is_strong_selfridge_prp	is_bpsw_prp	is_strong_bpsw_prp	is_prime (6.1.2)	is_prime (6.2.0)
100	1.00	1.42	0.92	5.71	11.18	10.28	11.35	10.14	12.04	11.65	11.47	30.38	11.24
150	1.00	0.66	0.65	3.07	11.66	6.75	6.67	6.63	6.61	7.03	9.06	21.33	9.65
200	1.00	1.07	1.01	3.68	8.64	8.40	7.78	7.23	8.64	11.48	8.31	27.30	4.26
300	1.00	1.26	1.08	3.13	6.24	8.64	9.23	3.09	3.20	4.66	4.39	14.36	3.58
400	1.00	1.00	1.27	2.32	4.33	4.51	4.60	4.22	4.19	5.37	5.42	19.92	3.88
500	1.00	0.98	1.13	2.58	5.30	5.54	5.25	4.92	4.83	5.95	5.91	24.88	4.97
750	1.00	1.09	1.02	2.36	4.94	4.88	4.87	4.80	4.60	5.66	5.68	25.89	4.40
1000	1.00	1.01	1.00	2.34	4.76	4.76	4.78	4.58	4.56	5.63	5.55	26.00	4.19
avg	1.00	1.06	1.01	3.15	7.13	6.72	6.81	5.70	6.08	7.18	6.97	23.76	5.77