mersenneforum.org > Math checking very large number for primality.
 Register FAQ Search Today's Posts Mark Forums Read

 2017-04-17, 11:40 #1 WhoCares   Apr 2017 216 Posts checking very large number for primality. Hey there. I will ask my question directly. n= some 1523 digits number. I want to check 10^n+7 is prime or not. I have used BigInteger class of c#, and I found that one factor of n is 11, that remains a 1522 digits number. However it seems it will be very long like a lifetime with a standard isPrime() function. Is there any way to do that quickly? (I am open to rent a super computer or something like that) Code: n= 39639600000000033079722130334105193516374462454515382070790605358914985114125041349652662917631491895468078068144227588488256698643731392656301687065828647039364869335097585180284485610320873304664240820377108832285808799206086668871981475355607012901091630830301025471386040357260999007608336089976844194508766126364538537876281839232550446576248759510420112471055243135957657955673172345352299040688058220310949388025140588819053919947072444591465431690373800860072775388686735031425736023817399933840555739331789612967251075090969235858418789282170029771749917300694674164737016209063843863711544823023486602712537214687396625868342705921270261329804829639431028779358253390671518359245782335428382401587826662256037049288785974197816738339397949057227919285478001984783327820046311610982467747270922924247436321534899106847502480979159775057889513728084684088653655309295401918623883559378101223949718822361892160105855110817069136619252398279854449222626529937148527952365200132318888521336420774065497849818061528283162421435659940456500165398610651670525967581872312272576910353953026794574925570625206748263314588157459477340390340721137942441283493218656963281508435329143235196824346675487925901422428051604366523321204101885544161429043996030433344359907376778035064505458154151505127356930201786304995038041680449884220972543830631822692689381409196162752232881243797552100562355276215679788289778365861726761495203440291101554746940125702944095269599735362222957327158451869004300363876943433675157128680119087
 2017-04-17, 11:53 #2 Nick     Dec 2012 The Netherlands 2·32·83 Posts No number of the form $$10^n+7$$ is divisible by 11. See, for example, these tests: https://en.wikipedia.org/wiki/Divisibility_rule
2017-04-17, 11:54   #3
WhoCares

Apr 2017

2 Posts

Quote:
 Originally Posted by Nick No number of the form $$10^n+7$$ is divisible by 11. See, for example, these tests: https://en.wikipedia.org/wiki/Divisibility_rule
I think u get me wrong. I said only n is divisible by 11.

2017-04-17, 12:02   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts

Quote:
 Originally Posted by WhoCares Hey there. I will ask my question directly. n= some 1523 digits number. I want to check 10^n+7 is prime or not. I have used BigInteger class of c#, and I found that one factor of n is 11, that remains a 1522 digits number. However it seems it will be very long like a lifetime with a standard isPrime() function. Is there any way to do that quickly? (I am open to rent a super computer or something like that) Code: n= 39639600000000033079722130334105193516374462454515382070790605358914985114125041349652662917631491895468078068144227588488256698643731392656301687065828647039364869335097585180284485610320873304664240820377108832285808799206086668871981475355607012901091630830301025471386040357260999007608336089976844194508766126364538537876281839232550446576248759510420112471055243135957657955673172345352299040688058220310949388025140588819053919947072444591465431690373800860072775388686735031425736023817399933840555739331789612967251075090969235858418789282170029771749917300694674164737016209063843863711544823023486602712537214687396625868342705921270261329804829639431028779358253390671518359245782335428382401587826662256037049288785974197816738339397949057227919285478001984783327820046311610982467747270922924247436321534899106847502480979159775057889513728084684088653655309295401918623883559378101223949718822361892160105855110817069136619252398279854449222626529937148527952365200132318888521336420774065497849818061528283162421435659940456500165398610651670525967581872312272576910353953026794574925570625206748263314588157459477340390340721137942441283493218656963281508435329143235196824346675487925901422428051604366523321204101885544161429043996030433344359907376778035064505458154151505127356930201786304995038041680449884220972543830631822692689381409196162752232881243797552100562355276215679788289778365861726761495203440291101554746940125702944095269599735362222957327158451869004300363876943433675157128680119087
modular exponentiation may help. Keeping in mind, you can mod the exponent by euler's totient function for the modulus. in you example 10^n+7 for mod 11 we get (-1)^n+7 as (-1)^n is either 1 or -1 we get a remainder of 6 or 8 and never 0.

2017-04-17, 12:03   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by WhoCares I think u get me wrong. I said only n is divisible by 11.
okay so which number's totient value is 11 ( if it can even happen edit:turns out it can't via istotient in PARI/gp) ? that should help you eliminate/prove a few factors of 10^n+7.

Last fiddled with by science_man_88 on 2017-04-17 at 12:04

 2017-04-17, 12:22 #6 Nick     Dec 2012 The Netherlands 2×32×83 Posts To get a general feel for what is possible, you could read this overview, which mentions several of the projects here: https://en.wikipedia.org/wiki/Genera...er_field_sieve
2017-04-17, 13:33   #7
Dr Sardonicus

Feb 2017
Nowhere

52×151 Posts

Quote:
 Originally Posted by WhoCares n= some 1523 digits number. I want to check 10^n+7 is prime or not. I have used BigInteger class of c#, and I found that one factor of n is 11, that remains a 1522 digits number. However it seems it will be very long like a lifetime with a standard isPrime() function. Is there any way to do that quickly? (I am open to rent a super computer or something like that)
If you want to determine whether n/11 is prime or composite (n the exponent), ispseudoprime() is much faster than isprime(), although it can only prove compositeness. If you want to determine whether 10^n+7 itself is prime, about all I can suggest offhand is to look for possible small prime factors p, checking whether Mod(10,p)^n + 7 == 0.

I'm not sure how factoring the exponent might help here, but I'm also not sure it won't
;-)

2017-04-17, 13:59   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts

Quote:
 Originally Posted by Dr Sardonicus If you want to determine whether n/11 is prime or composite (n the exponent), ispseudoprime() is much faster than isprime(), although it can only prove compositeness. If you want to determine whether 10^n+7 itself is prime, about all I can suggest offhand is to look for possible small prime factors p, checking whether Mod(10,p)^n + 7 == 0. I'm not sure how factoring the exponent might help here, but I'm also not sure it won't ;-)
you can speed that up in theory if you mod the exponent by p-1 as that's eulerphi of p for prime p. but here's a few results:

one part is even one part is odd so it doesn't divide by 2. both parts are 1 mod 3 so it doesn't divide by 3, the value is 2 mod 5 so it doesn't divide by 5. 3^n for any value n is not divisible by 7 so it won't divide by that. 11 has already shown not to divide into it. (-3)^n mod 13 cycles -3,9,-1,3,-9,1,-3 and none of these are -7 ( or +6 the equivalent) so it doesn't divide by 13. 17 produces (-7)^n+7 which goes 0,5,4,11,13,16,12,6,14,9,10,3,1,15,2,8, ... repeats which means if the exponent were 1 mod 16 it would divide however the exponent is 15 mod 16 it looks like. etc. edit:and once I felt like doing it it took under 1 minute to check all the way up to 2^30 that no primes divided it ( PARI/GP is pretty slow though at times).

Last fiddled with by science_man_88 on 2017-04-17 at 14:11

 2017-04-17, 14:23 #9 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×3×17×19 Posts A 1.5 k dd number should be matter of hours(if not minutes) with primo. You will get a certificate if prime. Don't necessarily give you the factor though. Last fiddled with by a1call on 2017-04-17 at 14:48
2017-04-17, 15:07   #10
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

915510 Posts

Quote:
 Originally Posted by WhoCares n= some 1523 digits number. I want to check 10^n+7 is prime or not.
There are in fact three alternatives: 10^n+7 is prime; 10^n+7 is not prime (composite); 10^n+7 is of unknown character.

You can find a factor for 10^n+7 by modular exponentiation but if not (which is fairly likely), then you will be stuck with the other two alternatives.

What is so special about that 10^n+7, though, - can you tell?

2017-04-17, 18:38   #11
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

10001011100012 Posts

Quote:
 Originally Posted by a1call A 1.5 k dd number should be matter of hours(if not minutes) with primo. You will get a certificate if prime. Don't necessarily give you the factor though.
You should re-read OP: the question is not whether 1520-digit n is prime (he says 11 is a factor, which should have been a hint...), but whether 10^n +7 is prime.

Consider that Prime95 tests numbers of magnitude 10^{8 digits}, or the very smallest 10^{9 digits}; then consider how long a prp test would take for 10^{1520+ digits}.

Finding a factor to show compositeness is OP's only hope.

Last fiddled with by VBCurtis on 2017-04-17 at 18:38

 Similar Threads Thread Thread Starter Forum Replies Last Post VolMike YAFU 18 2012-04-09 21:39 ixfd64 Math 12 2010-01-05 16:36 NeoGen Software 8 2006-03-20 01:22 Washuu Factoring 10 2005-08-11 05:09 fortega Data 2 2005-06-16 22:48

All times are UTC. The time now is 20:08.

Mon Nov 23 20:08:17 UTC 2020 up 74 days, 17:19, 3 users, load averages: 1.94, 2.43, 2.47