if p is prime, factors of 2^p-1? - Is it possible?

[ONeil]

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:

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'

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

[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.

[ONeil]

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.

[VBCurtis]

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.

[a1call]

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.

[ONeil]

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.

[VBCurtis]

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.

[a1call]

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

[VBCurtis]

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?

[a1call]

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]

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.