Number Theory Number Theory Math Forum

 October 10th, 2015, 12:14 PM #1 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 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. October 11th, 2015, 09:17 AM #2 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 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. October 11th, 2015, 09:19 AM #3 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 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. October 11th, 2015, 11:10 AM #4 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 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. October 11th, 2015, 12:17 PM #5 Senior Member   Joined: Dec 2007 Posts: 687 Thanks: 47 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. Thanks from mobel October 11th, 2015, 01:24 PM #6 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 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 October 11th, 2015, 02:26 PM   #7
Banned Camp

Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
 Originally Posted by al-mahed 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...). October 11th, 2015, 03:42 PM #8 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 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). October 11th, 2015, 09:22 PM   #9
Senior Member

Joined: Dec 2007

Posts: 687
Thanks: 47

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 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 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. October 12th, 2015, 01:50 AM #10 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 @Al-Mahed Why 341 as example? You have to read this thread : New primality test I proposed a new primality test so 341 is a number failing my test. I called Fermat pseudo-prime number base 2 instead of calling it Mobel pseudo-prime. Charles will understand what I`m talking about because he intervenes in that thread. All my threads are linked in some way or another. My interests : primes, semi-prime numbers, factorization, integer sequences, combinatorics, puzzles .... Thanks from al-mahed Tags breaking, fermat, news, pseudoprimes ,

### fermat numbers news

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post fafa Number Theory 4 July 10th, 2013 11:25 AM usermind Number Theory 1 October 5th, 2010 09:30 AM Mathworm Abstract Algebra 1 March 5th, 2009 02:20 PM reddmann Number Theory 2 August 30th, 2007 08:03 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      