20170417, 11:40  #1 
Apr 2017
2 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 
20170417, 11:53  #2 
Dec 2012
The Netherlands
1,621 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 
20170417, 11:54  #3  
Apr 2017
2 Posts 
Quote:


20170417, 12:02  #4  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


20170417, 12:03  #5 
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
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 20170417 at 12:04 
20170417, 12:22  #6 
Dec 2012
The Netherlands
1,621 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 
20170417, 13:33  #7  
Feb 2017
Nowhere
2^{4}·271 Posts 
Quote:
I'm not sure how factoring the exponent might help here, but I'm also not sure it won't ;) 

20170417, 13:59  #8  
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Quote:
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 20170417 at 14:11 

20170417, 14:23  #9 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{6}·31 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 20170417 at 14:48 
20170417, 15:07  #10  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·3·5·311 Posts 
Quote:
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? 

20170417, 18:38  #11  
"Curtis"
Feb 2005
Riverside, CA
11103_{8} Posts 
Quote:
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 20170417 at 18:38 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Bug with particular large number  VolMike  YAFU  18  20120409 21:39 
Wagstaff number primality test?  ixfd64  Math  12  20100105 16:36 
newbie question  testing primality of very large numbers  NeoGen  Software  8  20060320 01:22 
is GGNFS checking for SNFS number?  Washuu  Factoring  10  20050811 05:09 
checking smaller number  fortega  Data  2  20050616 22:48 