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.