My Math Forum Breaking news : Fermat pseudo-primes

 Number Theory Number Theory Math Forum

 October 12th, 2015, 02:24 AM #11 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 2^340 mod 341=1 I do not understand you. Either you read quickly what I wrote either you are talking about something else. Im not talking about the Fermat numbers https://en.wikipedia.org/wiki/Fermat_number Im talking about the Fermat pseudo-primes base 2 https://en.wikipedia.org/wiki/Fermat_pseudoprime
October 12th, 2015, 05:28 AM   #12
Senior Member

Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
 Originally Posted by mobel @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 Im 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 ....
So in that case you are in good hands, CRG is specialized in this and Mersene Numbers, which is a close topic.

Now I see you want to treat general cases of pseudo-primality, like 341, using that other sequence, which I baptized as "Mobel Sequence" after you. Now I see what you want .

I recall that I proved what term should be divisible by $p$ in those sequences, so I'll continue this discussion in that topic in regard to the proof as given in:

Conjecture "2^n"

 October 12th, 2015, 06:05 AM #13 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 I started by the sequence conjecture 2^n. Then I found a new (?) primality test which equivalent to Fermat test. Some numbers failed my test. Then come the question on filtering out those numbers. I have found the algorithm on how to filter out those numbers. I did not implement the algorithm so I do not know its algorithmic complexity. Im not programmer. I use Excel plus paper and pen. Thats it. In any case I solved theoretically the problem. I have found today a particular link between 2 sequences. The question now on the table is : can we use my primality test to factorize odd numbers?
October 12th, 2015, 06:29 AM   #14
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
 Originally Posted by mobel 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.
Your method requires factoring p-1 completely in order to prove that p is prime, and as such its complexity is astronomical. For example, factoring a hard 300-digit number would take millions of dollars of effort with the best-available methods, while checking the primality of a 300-digit number takes a second or two on my machine.

Quote:
 Originally Posted by mobel 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.
You've reduced an easy problem to a very hard one. But it was already known that the factorization of p-1 allows for a quick test of the primality of p. Further, in the 1970s Brillhart, Lehmer, and Selfridge improved this test so that you only needed a partial factorization of p-1 to prove the primality of p, so there's a much better way already.

October 12th, 2015, 06:38 AM   #15
Banned Camp

Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
 Originally Posted by CRGreathouse Your method requires factoring p-1 completely in order to prove that p is prime, and as such its complexity is astronomical. For example, factoring a hard 300-digit number would take millions of dollars of effort with the best-available methods, while checking the primality of a 300-digit number takes a second or two on my machine. You've reduced an easy problem to a very hard one. But it was already known that the factorization of p-1 allows for a quick test of the primality of p. Further, in the 1970s Brillhart, Lehmer, and Selfridge improved this test so that you only needed a partial factorization of p-1 to prove the primality of p, so there's a much better way already.
Did you read everything before commenting.
You are commenting this step but many things came after that.
Nothing astronomical.

October 12th, 2015, 06:53 AM   #16
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
 Originally Posted by mobel Did you read everything before commenting.
Yes.

 October 13th, 2015, 06:57 AM #17 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 There is no need to factorize n-1. All you need to know is n-1 odd or even If it is even then you split in 2. As long as it is even you continue splitting in 2. n=341 n-1=340 340 is even I split in 170-170 I compute : 2^340-1=(2^170-1)*(2^170+1) I have two factors : f1=2^170-1 and f2=2^170+1 I compute gcd(f1,n)=gcd(2^170-1,n)=341 gcd(f2,2^170+1)=1 At this step I remove f2 because none of its factors divide 341 Hence I continue only with f1=2^170-1 Now it 170 odd or even 170 is even 170=85+85 Hence : 2^170-1=(2^85-1)*(2^85+1) f3=2^85-1 f4=2^85+1 I compute 2 gcds : gcd(2^85-1,341)=31 gcd(2^85+1,341)=11 Hence 341 is composite = 31*11 If you understand this algorithm then you will not need to know the factorization of n-1 to filter out the Fermat pseudo-primes. If 2^t-1 with t odd I have the solution too. Many Fermat pseudo prime numbers (like 341 and others) will be eliminated before reaching the step of odd exponents. Last edited by mobel; October 13th, 2015 at 07:14 AM.
 October 13th, 2015, 07:13 AM #18 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 There is NO need to factorize n-1. I repeat it and I will repeat it twice. Some primality tests require factorizing n-1. When I say factorizing I mean finding all the primes dividing n-1. I do not need that. I propose a binary research : You plit in 2. You compute 2 gcds. Either the 2 will show that n is composite Either one of them will be removed from the research and we continue with the other who gcd (n,fi)=n *fi is the dactor not in the sens of the particular divisor). As long you do not distinguish the 2 : the polynomial factor of the 2^s+1 or 2^s-1) and the individual prime diving n-1 (p1,p2,...pk) you could not understand my test.
 October 13th, 2015, 07:16 AM #19 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 If this not a definitive solution of filtering out the Fermat pseudo-prime numbers I will stop everything and go to spend my time with birds and donkeys.
 October 13th, 2015, 07:52 AM #20 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 When some primality tests require the factorization of n-1 it is not a problem but when Mobel talks about the "factorization" of n-1 it becomes astronomical and so on. The way I look to the factorization is DIFFERENT. n-1 is a product of (2^k(*(odd number) I do not need to go on details of the factors (the final divisors). My conclusion is that no one read carefully what is written. Behaving like robots is the main behaviour. Fermat? and the guy start talking about the Fermat prime numbers instead of talking about Fermat pseudo-prime numbers. 561 as I indicate does not FAIL to my test but it fails to Fermat test. He said I was wrong but no one corrected it. Factorization? what? what? it is ASTRONOMICAL!!!!!!!!!!! Because I`m Mobel. But if others use it then it is NOT astronomical it is doable. Better for me to stop posting.

 Tags breaking, fermat, news, pseudoprimes

,

### fermat numbers news

Click on a term to search for related topics.
 Thread Tools Display Modes Linear 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