My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree5Thanks
Reply
 
LinkBack Thread Tools Display Modes
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.

I`m not talking about the Fermat numbers
https://en.wikipedia.org/wiki/Fermat_number

I`m talking about the Fermat pseudo-primes base 2

https://en.wikipedia.org/wiki/Fermat_pseudoprime
mobel is offline  
 
October 12th, 2015, 05:28 AM   #12
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
Originally Posted by mobel View Post
@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 ....
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"
al-mahed is offline  
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.
I`m not programmer. I use Excel plus paper and pen. That`s 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?
mobel is offline  
October 12th, 2015, 06:29 AM   #14
Global Moderator
 
CRGreathouse's Avatar
 
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 View Post
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 View Post
If there is some omission or mistaping please correct it. I`m 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.
CRGreathouse is offline  
October 12th, 2015, 06:38 AM   #15
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
Originally Posted by CRGreathouse View Post
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.
Read first and then comment please.
mobel is offline  
October 12th, 2015, 06:53 AM   #16
Global Moderator
 
CRGreathouse's Avatar
 
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 View Post
Did you read everything before commenting.
Yes.
CRGreathouse is offline  
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 gcd`s :
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.
mobel is offline  
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 gcd`s.
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.
mobel is offline  
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.
mobel is offline  
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.
mobel is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
breaking, fermat, news, pseudoprimes



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fermat primes fafa Number Theory 4 July 10th, 2013 11:25 AM
Problems driving me crazy.(Primes,Fermat,Euler) usermind Number Theory 1 October 5th, 2010 09:30 AM
Pseudo-finite fields Mathworm Abstract Algebra 1 March 5th, 2009 02:20 PM
Pseudo-Diophantine Nuisance reddmann Number Theory 2 August 30th, 2007 08:03 AM





Copyright © 2018 My Math Forum. All rights reserved.