mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2017-04-17, 11:40   #1
WhoCares
 
Apr 2017

2 Posts
Lightbulb 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
WhoCares is offline   Reply With Quote
Old 2017-04-17, 11:53   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

5×13×23 Posts
Default

No number of the form \(10^n+7\) is divisible by 11.
See, for example, these tests:
https://en.wikipedia.org/wiki/Divisibility_rule
Nick is online now   Reply With Quote
Old 2017-04-17, 11:54   #3
WhoCares
 
Apr 2017

102 Posts
Default

Quote:
Originally Posted by Nick View Post
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.
WhoCares is offline   Reply With Quote
Old 2017-04-17, 12:02   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

Quote:
Originally Posted by WhoCares View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-04-17, 12:03   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

Quote:
Originally Posted by WhoCares View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-04-17, 12:22   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

5×13×23 Posts
Default

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
Nick is online now   Reply With Quote
Old 2017-04-17, 13:33   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

EC516 Posts
Default

Quote:
Originally Posted by WhoCares View Post
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
;-)
Dr Sardonicus is offline   Reply With Quote
Old 2017-04-17, 13:59   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-04-17, 14:23   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

79316 Posts
Default

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
a1call is offline   Reply With Quote
Old 2017-04-17, 15:07   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×3×7×109 Posts
Default

Quote:
Originally Posted by WhoCares View Post
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?
Batalov is offline   Reply With Quote
Old 2017-04-17, 18:38   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

446610 Posts
Default

Quote:
Originally Posted by a1call View Post
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
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bug with particular large number VolMike YAFU 18 2012-04-09 21:39
Wagstaff number primality test? ixfd64 Math 12 2010-01-05 16:36
newbie question - testing primality of very large numbers NeoGen Software 8 2006-03-20 01:22
is GGNFS checking for SNFS number? Washuu Factoring 10 2005-08-11 05:09
checking smaller number fortega Data 2 2005-06-16 22:48

All times are UTC. The time now is 16:10.

Tue Nov 24 16:10:15 UTC 2020 up 75 days, 13:21, 4 users, load averages: 1.50, 1.65, 1.69

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