checking very large number for primality.

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

n= 39639600000000033079722130334105193516374462454515382070790605358914985114125041349652662917631491895468078068144227588488256698643731392656301687065828647039364869335097585180284485610320873304664240820377108832285808799206086668871981475355607012901091630830301025471386040357260999007608336089976844194508766126364538537876281839232550446576248759510420112471055243135957657955673172345352299040688058220310949388025140588819053919947072444591465431690373800860072775388686735031425736023817399933840555739331789612967251075090969235858418789282170029771749917300694674164737016209063843863711544823023486602712537214687396625868342705921270261329804829639431028779358253390671518359245782335428382401587826662256037049288785974197816738339397949057227919285478001984783327820046311610982467747270922924247436321534899106847502480979159775057889513728084684088653655309295401918623883559378101223949718822361892160105855110817069136619252398279854449222626529937148527952365200132318888521336420774065497849818061528283162421435659940456500165398610651670525967581872312272576910353953026794574925570625206748263314588157459477340390340721137942441283493218656963281508435329143235196824346675487925901422428051604366523321204101885544161429043996030433344359907376778035064505458154151505127356930201786304995038041680449884220972543830631822692689381409196162752232881243797552100562355276215679788289778365861726761495203440291101554746940125702944095269599735362222957327158451869004300363876943433675157128680119087

[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

[WhoCares]

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.

[science_man_88]

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)

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.

[science_man_88]

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.

[Nick]

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

[Dr Sardonicus]

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
;-)

[science_man_88]

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

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

[Batalov]

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?

[VBCurtis]

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.