mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > ONeil

Closed Thread
 
Thread Tools
Old 2020-10-23, 00:19   #1
ONeil
 
ONeil's Avatar
 
Dec 2017

2×3×52 Posts
Question if p is prime, factors of 2^p-1? - Is it possible?

Ok according to the mods and some users "Factor this" was a disaster, so they locked the thread. Yet is it all lost or not. So I got to thinking and some here would say that is a dangerous thing lol :). I have a big question for some of the python programmers here.

As you may or may not know all factors of prime numbers which use this formula 2^p-1 when p is prime and 2^p-1 does not produce a prime, the factor is prime.

Would it be possible to use a text file with many prime numbers and then access it instantaneously and apply modular arithmetic to instantly find a factor for '2^p-1' if 'p' is a prime number while using 2^p-1 and that does not produce a prime number

this is what's in my text file:

k=(3,5,7,11,13,17,19,23, 47, 223, 233)

Here is the code I have so far but its throwing this error:

Quote:
File "Factor This.py", line 6, in <module>
if (2**p-1) % (open("C:\python37\k.txt"),'r') == 0:
TypeError: unsupported operand type(s) for %: 'int' and 'tuple'

Code:
import timeit
while True:
	p = int(input("Enter a prime number: "))
	start_time = timeit.default_timer()
	for k in range(3,300,2):
		if (2**p-1) % (open("C:\python37\k.txt"),'r') == 0:
			print(k)
			print(timeit.default_timer() - start_time,'seconds')
			break

Last fiddled with by ONeil on 2020-10-23 at 00:25
ONeil is offline  
Old 2020-10-23, 00:34   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×19×23 Posts
Default

Learn to program. Get yourself an elementary book on Python.

I do not know Python. It does have set membership and arrays. I guess Python, like may other languages, requires you to open the file and the loop over the stream until the end of the file and then close it. So you could open the file and read in the vector. Whether you can take a "%" over a vector I am not sure.

Somebody else who is knowledgeable about this language will jump in and put you right.

Last fiddled with by paulunderwood on 2020-10-23 at 00:38
paulunderwood is offline  
Old 2020-10-23, 00:39   #3
ONeil
 
ONeil's Avatar
 
Dec 2017

2268 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Learn to program. Get yourself an elementary book on Python.

I do not know Python. It does have set membership and arrays. I guess Python, like may other languages requires you to open the file and the loop over the stream until the end of the file and then close it. So you could open the file and read in the vector. Whether you can take a "%" over a vector I am not sure.

Somebody else who is knowledgeable about this language will jump in and put you right.
Thanks Paul

I think it is possible I'm just worried about speed, if it does it in a flash then I think its worth pursuing. I can imagine the text file could be very large tho yet if you can test large digit primes and say one inputs an 8 digit prime to test and then a factor comes back in a flash then you can move on to another test.
ONeil is offline  
Old 2020-10-23, 01:42   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

112·37 Posts
Default

You can move on to other tests already- all of the factors your methods could find have already been found for exponents below 4 billion or so.

You haven't the slightest idea of the mathematics of mersenne factors, nor how to program- so you're writing really slow code that does really slow algorithms to factor.

If you want fast factors of mersennes, use factor5, or Prime95. Or, read the most basic properties of mersenne factors.

Your first statement isn't even true- not every factor of 2^p-1 is prime. Some are composite, really.
VBCurtis is offline  
Old 2020-10-23, 01:49   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7×277 Posts
Default

I think what he is referring to is that a factor of 2^p-1 is prime if (single"f") it is equal to 2p+1.
a1call is offline  
Old 2020-10-23, 02:11   #6
ONeil
 
ONeil's Avatar
 
Dec 2017

2×3×52 Posts
Default

Yes there is always a single factor for one of them is prime. This is a worth while venture if the returns are fast. Think about it I can spend the time to print out a list of big primes into a text file beyond the ones that are found. Then simply type a number 8 to 9 digits as a prime number and it it returns quickly as a factor then we have something otherwise I agree with you VB if time does not permit this.

VBCurtis you should really expand your mind a little and like these fresh well thought out creative experiments they do leed to greatness sometimes. I not saying we or I am there yet, but who knows what if we get the speeeeeeeeeeeed.


Last fiddled with by ONeil on 2020-10-23 at 02:13
ONeil is offline  
Old 2020-10-23, 02:30   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

112×37 Posts
Default

We already have the speed. You don't. Your methods are slow, and reflect no comprehension of factoring.

You don't even grasp how long it would take to read primes from a text file, versus generate them live via code. You think reading a file is "instant". It's not, not even a little bit.

"I'm so ignorant I might be a genius" is a special sort of argument. We have a name for that flavor of ignorance, too.

Last fiddled with by VBCurtis on 2020-10-23 at 02:32
VBCurtis is offline  
Old 2020-10-23, 02:32   #8
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7×277 Posts
Default

To see if 2p+1 divides 2*p-1 is computationally about as expensive as a PRP test. It is deterministic but not much, much faster than a PRP test and then a N-1 test.
I learned about it from SM and here is an old relevant thread:

https://www.mersenneforum.org/showthread.php?t=24964

Last fiddled with by a1call on 2020-10-23 at 02:33
a1call is offline  
Old 2020-10-23, 02:35   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

112×37 Posts
Default

Quote:
Originally Posted by a1call View Post
To see if 2p+1 divides 2*p-1 is computationally about as expensive as a PRP test.
You also fail at a grasp of mersenne factoring.

Hint: testing k=1 in trial factoring, versus a prp test. No ,not the same computational length. No.

Edit: Wait, do you mean 2*p-1, or 2^p-1? If you mean 2*p-1, how is 2p+1 going to divide 2p-1, which is smaller? Eh?

Last fiddled with by VBCurtis on 2020-10-23 at 02:37
VBCurtis is offline  
Old 2020-10-23, 02:53   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7·277 Posts
Default

Meant 2^p-1
If for any prime p
2*p+1 | 2^p-1
Then 2*p+1 is definitely prime.
The test is deterministic and computationally about as expensive as a PRP test.
a1call is offline  
Old 2020-10-23, 02:55   #11
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7×277 Posts
Default

Meant 2^p-1
If for any prime p
2*p+1 | 2^p-1
Then 2*p+1 is definitely prime.
The test is deterministic and computationally about as expensive as a PRP test for 2*p+1.
The time saved is not significant.
Sorry for the double post. Was not intentional.

Last fiddled with by a1call on 2020-10-23 at 02:56
a1call is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
largest n such that n^2+1 has prime factors within a set fivemack Abstract Algebra & Algebraic Number Theory 8 2020-10-01 14:36
Checking that there are no prime factors up to x CRGreathouse Math 14 2017-09-22 16:00
Prime factors of googolplex - 10. Arkadiusz Factoring 6 2011-12-10 15:16
Are all factors prime? kurtulmehtap Math 4 2010-09-02 19:51
Distribution of Mersenne prime factors mod 6 alpertron Math 0 2006-06-23 20:07

All times are UTC. The time now is 18:50.

Thu Nov 26 18:50:55 UTC 2020 up 77 days, 16:01, 3 users, load averages: 2.17, 2.02, 1.71

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.