mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   I Think I Have A Primality test based on the Lehmer´s totient problem (https://www.mersenneforum.org/showthread.php?t=24201)

MathDoggy 2019-03-24 13:01

I Think I Have A Primality test based on the Lehmer´s totient problem
 
Introduction: Lehmer´s totient problem is a mathematical assertion which states that there does not exist a composite positive integer x that satisfies the following:

Let f(x) be Euler´s phi function
Property that composite numbers do not satisfy:
f(x) divides x-1

If this conjecture was proved I could formulate a primality test based on Lehmer´s problem,the primality test would be as follows:

Let x be a positive integer

If f(x) divides x-1 return PRIME
If f(x) does not divide x-1 return COMPOSITE

Well this was what I wanted to share, thank you for reading

CRGreathouse 2019-03-24 13:13

I can improve your test. This works without assuming Lehmer's conjecture:

Let x be a positive integer.

If f(x) = x-1 return PRIME
If f(x) < x-1 return COMPOSITE
If f(x) > x-1 return UNIT

Now all you have to do is find a way to compute f(x) quickly and you're done!

R. Gerbicz 2019-03-24 13:26

[QUOTE=CRGreathouse;511652]
Now all you have to do is find a way to compute f(x) quickly and you're done![/QUOTE]

Much more is known. In fact if you know a "small" multiple of eulerphi(n) then you can factorize in polynomial time.

a1call 2019-03-24 13:35

[QUOTE=MathDoggy;511651]

Well this was what I wanted to share, thank you for reading[/QUOTE]


Thank you very much for sharing that. I was not aware of that open problem. Quite an interesting subject.

ETA it is interesting how different
f(x) | x+1
Relates.

MathDoggy 2019-03-24 23:27

I found an algorithm to find the values of the phi function.
Algorithm:


1-gc <- function (m, n) {
2- while (1) {
3- rem <- m %% n # getting the remainder here
4- ifelse (rem == 0, break, { m = n; n = rem; })
5- }
6- n
7-}
8-
9-# eulers phi function
10-phi <- function (n) {
11- if (n < 0) { -1 } # function's domain are positive integers only
12- sum = 0
13- for (k in 1:n) {
14- if (gc(n, k) == 1) { sum = sum + 1 }
15- } # k is a totient of n.
16-}
17-
18-value <- NULL
19-for (i in 1:1000) {
20-value <- c(val

This can be programmed in C++, I don´t know if the algorithm is fast

MathDoggy 2019-04-13 15:53

Counterexample to Lehmer's totient problem
2^521-1 is prime and when you put in the Phi function it is not equal to (2^521-1)-1 as Lehmer conjectured

Batalov 2019-04-13 16:01

[QUOTE=MathDoggy;513609][STRIKE]Counterexample to Lehmer's totient problem[/STRIKE]
2^521-1 is prime and when you put in the Phi function it is not equal to (2^521-1)-1 [STRIKE]as Lehmer conjectured[/STRIKE][/QUOTE]
"This is worse than a crime; this is a mistake." (Joseph Fouche)

MathDoggy 2019-04-15 13:11

[QUOTE=MathDoggy;513609]Counterexample to Lehmer's totient problem
2^521-1 is prime and when you put in the Phi function it is not equal to (2^521-1)-1 as Lehmer conjectured[/QUOTE]

I see the mistake

dcheuk 2019-04-17 03:04

[QUOTE=MathDoggy;513609]Counterexample to Lehmer's totient problem
2^521-1 is prime and when you put in the Phi function it is not equal to (2^521-1)-1 as Lehmer conjectured[/QUOTE]

I am confounded. We all know that [$]p\in\text{prime}\implies\phi(p)=p-1[/$], recall that the group of units for any prime number p has order (p-1).

How so that [$]\phi\big(2^{521}-1\big)\neq(2^{521}-1)-1[/$] but [$]2^{521}-1[/$] is a prime?


All times are UTC. The time now is 04:16.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.