My Math Forum (http://mymathforum.com/math-forums.php)
-   Number Theory (http://mymathforum.com/number-theory/)
-   -   Breaking news : Fermat pseudo-primes (http://mymathforum.com/number-theory/221218-breaking-news-fermat-pseudo-primes.html)

 mobel October 10th, 2015 01:14 PM

Breaking news : Fermat pseudo-primes

Hi girls and guys,

Finally I have found a way to filter out all the Fermat pseudo-primes!!!!!!!!!!!
Easy to do it.
Try to rethink the Fermat test.
Forget all what you learned about it.
Try to find an elementary proof of little Fermat theorem.

See you later.

 mobel October 11th, 2015 10:17 AM

Why 341 is a Fermat pseudo-prime?
When we compute

2^340-1 mod 341 is equal to zero

But if we decompose
2^340-1
in factors
then we could write :

2^340-1=(2^170+1)*(2^170-1)
or
2^340-1=(2^170+1)*(2^85+1)*(2^85-1)

we could continue factorizing until we find no other factor than those computed.

Im not going to find all the factors but just what I need to show that 341 is composite.

By compute the gcds I will show that 341 is composite number

gcd(2^85+1,341)=33

33 is > 1 and < 341 hence 341 is composite.

I can continue :

gcd(2^85-1,341)=31

Check test :

2^170-1 mod 341 = 0
2^170+1 mod 341 = 2

2^85+1 mod 341=3*11
2^85-1 mod 341=31

I gave this example but it is valid for any Fermat pseudo-prime number base 2

For n we compute 2^(n-1) mod n
if 2^(n-1) mod n = 1 then n could be either prime or pseudo-prime.

As all the prime numbers (>3) could be expressed in the form 6k+1 or 6k-1
hence

2^(n-1)=2^(6k+1-1)=2^(6k)
or
2^(n-1)=2^(6k-1-1)=2^(6k-2)=2^(2*(2k-1))

In both cases we can factorize them using polynomial factoring of 2 forms :

X^2-Y^2

or

X^(2t+1)+ or -Y(2t+1)

There are algorithm doing this job

Once we have all the polynomial factors (f1,f2,f3,....fm) we should compute

gcd(f1,n)
gcd(f2,n)
gcd(f3,n)
.....
gcd(fm,n)

if one of those gcd give a value between 1 and n then n is surely composite otherwise is certified prime.

I do not know the algorithmic complexity of such algorithm when n is large.

Ps : If there is some omission or mistaping please correct it. Im too ill to focus on details but the primality problem is solved for ever.

 mobel October 11th, 2015 10:19 AM

If someone can put all what I said above in technical form (Latex and so one) it will be helpful. Anyone can read it without any discomfort.
The problem is definitely solved.

Any question will be welcomed.

 mobel October 11th, 2015 12:10 PM

I need to know if there is a way or formula to compute the number of distinct primes dividing (2^(n!))-1

Example :

15 distinct primes divide (2^(5!))-1
6 distinct primes divide (2^(4!))-1

I do not need the exact value but just an approximation.

I need it to solve another problem.

Thank you for any doc or clue or formula or URL.
It is not an emergency.

 al-mahed October 11th, 2015 01:17 PM

Hi Mobel.

So lets fix some terminology. Taking the modular equation $a^{n-1}\equiv 1\pmod n$, we define: a pseudo-prime $n$ is a composite number such that the aforementioned equation holds for $a=2$.

Now, an interesting fact: if $n$ is a pseudo-prime, then $2^n-1$ is also a pseudo-prime. This means: $2^{2^n-1}\equiv 1\pmod{2^n-1}$.

A Fermat number is a number of the form $2^{2^k}+1$, so we are talking about different things because, in this case, for $2^{2^k}+1=n$ where $n$ is a pseudo-prime, we have $2^{2^{2^k}}\equiv 1\pmod{2^{2^k}+1}$.

Now if you plug it in the first identity you will get an increasing amount of powers of two, I mean, if $2^{2^k}+1$ is a pseudo-prime, then
$$2^{2^{2^{2^k}+1}-1}\equiv 1\pmod{2^{2^{2^k}+1}-1}$$.

But that seems to lead to nowhere, because it gets an infinite sequence of raising powers which grows pretty quickly in computational complexity. This means that factorizing it is unpractical.

 mobel October 11th, 2015 02:24 PM

It seems impractical at first glance.
Factoring 2^(2*n)-1 or 2^(3*n)-1 is impractical if we want to find all the factors.
But if we need only one factor then we have to find a way to reach quickly.
How can we do that?

n=341

2^340 - 1 = (2^170+1)*(2^170-1)
That is the first step
2^340-1=(2^170+1)*(2^85+1)*(2^85-1)
That is a part the second level because
2^85+1 can be factorized as (2^17)^5+1^5 =(2+1)*some stuff

There are even parts and odd parts on 340=4*85 (4 is the even part and 85 the odd part).

As we go from the first level to the level below of factorization we will find that a factor giving us the solution.

It deserves to be studied to make sure that n is finally composite without any doubt.
Im aware of the hurdles. Im not dumb.
Unfortunately Im not programmer to test some Fermat pseudo-primes numbers to see if there is a pattern to exploit to get the job done.

My solution is definitive. No one can tell that it will not lead to the solution.
It is time to improve the second part of the algorithm.
I can not do it alone.
While working on that problem I deeply think that we could use the Fermat test improved to factorize any odd number.

Im waiting for other comments.

Thank you Al-Mahed

 mobel October 11th, 2015 03:26 PM

Quote:
 Originally Posted by al-mahed (Post 408467) Hi Mobel. So lets fix some terminology. Taking the modular equation $a^{n-1}\equiv 1\pmod n$, we define: a pseudo-prime $n$ is a composite number such that the aforementioned equation holds for $a=2$. Now, an interesting fact: if $n$ is a pseudo-prime, then $2^n-1$ is also a pseudo-prime. This means: $2^{2^n-1}\equiv 1\pmod{2^n-1}$. A Fermat number is a number of the form $2^{2^k}+1$, so we are talking about different things because, in this case, for $2^{2^k}+1=n$ where $n$ is a pseudo-prime, we have $2^{2^{2^k}}\equiv 1\pmod{2^{2^k}+1}$. Now if you plug it in the first identity you will get an increasing amount of powers of two, I mean, if $2^{2^k}+1$ is a pseudo-prime, then $$2^{2^{2^{2^k}+1}-1}\equiv 1\pmod{2^{2^{2^k}+1}-1}$$. But that seems to lead to nowhere, because it gets an infinite sequence of raising powers which grows pretty quickly in computational complexity. This means that factorizing it is unpractical.
It seems to me that you did not read carefully what I said above.
The number of factors of 2^(n-1)-1 when n is a Fermat pseudo-prime base 2 are finite. Only one factor will allow us to find the solution. In fact there are many. How to detect which one is not an unsolvable problem. Just think little bit about it.
Stay focused on the problem. It seems to me that you have taken another having nothing to do with my problem.
If n is pseudo-prime then for sure (2^n)-1 is composite. As n is odd (2^n)-1 is composite and can be factorized as difference of odd powers X^n-Y^n (like X^3-Y^3 or X^21-Y^21 etc...).

 mobel October 11th, 2015 04:42 PM

I got it!!!!!!!!!!!!!!!!
n=341

2^(341-1)-1 = (2^340)-1
= (2^170+1)*(2^170-1)

When we compute gcd(2^170+1,341)=1 hence we do not need to factor 2^170+1
But gcd(2^170-1,341)=341 hence we will continue to factor 2^170-1

2^170-1=(2^85+1)*(2^85-1)

What is gcd(2^85+1,341)=11 hence 11 divide 341 end 341 is composite 341=11*31

So the research will some sort of binary research.
It will speed the test.
Important : keep in mind that there is a difference between the polynomial factors and the divisors.
2^85+1 is one factor but it is equal to the product of 4 primes 3*11*43691*26831423036065352611

The solution is almost complete.
We need to evaluate the algorithm complexity when n become large.
The hurdle will be the factorization of n-1.
If n-1 is product of small factors then we could solve easily the problem.
If n-1 is a product of large numbers then we will have a serious problem.
As the (n-1)s of Fermat pseudo primes are often product of small factors I do not think that it will be a problem at least for some lower size (200 digits more I do not know).

 al-mahed October 11th, 2015 10:22 PM

Hi Mobel, I misread your posts so mea culpa, I assumed you asked for some methods. But I was also confused, you said that 341 is a Fermat pseudo-prime, this is very wrong since 340 is not a power of 2.

I'll just comment your last post.

Quote:
 Originally Posted by mobel (Post 408483) Only one factor will allow us to find the solution. In fact there are many. How to detect which one is not an unsolvable problem. Just think little bit about it.
This is true for any test of primality, you just need to find one factor to prove a number not being prime. The issues here are several: you can test it, surely, for any pseudo-prime number, but if it is too big the first problem would be to compute the remainder and to decide if $2^{n-1}\equiv 1\pmod n$ holds, the second problem would be to verify whether $n$ is composite. Suppose it is prime, then you might have extra work to do since you won't find any factor, and you are reduced to the known methods to test primality.

Quote:
 Originally Posted by mobel (Post 408483) Stay focused on the problem. It seems to me that you have taken another having nothing to do with my problem. If n is pseudo-prime then for sure (2^n)-1 is composite. As n is odd (2^n)-1 is composite and can be factorized as difference of odd powers X^n-Y^n (like X^3-Y^3 or X^21-Y^21 etc...).
This is trivial, Mobel. Furthermore, I think you are referring to $2^{n-1}-1$ because by definition $2^{n-1}\equiv 1\pmod n$.

Basically your test boils down to factor the exponent $n-1$ in $2^{n-1}-1^{n-1}$ by writing it as a difference of two powers, so this is again the very same problem in complexity terms, i.e., to factor $n$ which is "as big" as $n-1$.

Now, since you are working with Fermat numbers, $n-1$ will be a power of 2 and this greatly simplify things in this respect, there is really no big issue in dividing by 2 until reaching 1. In this case you are testing whether $2^{F_k-1}\equiv 1\pmod{F_k}$, where $F_k=2^{2^{k}}+1$ is your Fermat number. Write $2^{F_k-1}-1=2^{F_k-1}-1^{F_k-1}=2^{2^{2^{k}}}-1^{2^{2^{k}}}$ and your factors are simply
$$2^{\frac{2^{2^{k}-\ell}}{2^\ell}}-1^{\frac{2^{2^{k}-\ell}}{2^\ell}}.$$

You then must have all these factors, which are very easy to compute. But, is this a test of $F_k$ being a pseudo-prime? You could multiply these factors and see if some subset of them is divisible by $F_k$, clearly none can be exactly $F_k$. But this looks complicated, although there is perhaps a way using what I suggested.

After working in some details lots of complication appeared, so once I have something better I post here. If any detail is misunderstood please point out.

 mobel October 12th, 2015 02:50 AM

@Al-Mahed

Why 341 as example?