mersenneforum.org if p is prime, factors of 2^p-1? - Is it possible?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2020-10-23, 00:19   #1
ONeil

Dec 2017

24×3×5 Posts
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 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

 2020-10-23, 00:34 #2 paulunderwood     Sep 2002 Database er0rr E2216 Posts 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
2020-10-23, 00:39   #3
ONeil

Dec 2017

24·3·5 Posts

Quote:
 Originally Posted by paulunderwood 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.

 2020-10-23, 01:42 #4 VBCurtis     "Curtis" Feb 2005 Riverside, CA 10010100000012 Posts 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.
 2020-10-23, 01:49 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·17·59 Posts 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.
 2020-10-23, 02:11 #6 ONeil   Dec 2017 24·3·5 Posts 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
 2020-10-23, 02:30 #7 VBCurtis     "Curtis" Feb 2005 Riverside, CA 3·1,579 Posts 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
 2020-10-23, 02:32 #8 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×17×59 Posts 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
2020-10-23, 02:35   #9
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

3·1,579 Posts

Quote:
 Originally Posted by a1call 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

 2020-10-23, 02:53 #10 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 200610 Posts 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.
 2020-10-23, 02:55 #11 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·17·59 Posts 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

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Abstract Algebra & Algebraic Number Theory 8 2020-10-01 14:36 CRGreathouse Math 14 2017-09-22 16:00 Arkadiusz Factoring 6 2011-12-10 15:16 kurtulmehtap Math 4 2010-09-02 19:51 alpertron Math 0 2006-06-23 20:07

All times are UTC. The time now is 00:37.

Sun Apr 18 00:37:54 UTC 2021 up 9 days, 19:18, 0 users, load averages: 2.43, 2.13, 2.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.