mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > storflyt32

Reply
 
Thread Tools
Old 2014-10-20, 15:56   #12
storflyt32
 
Feb 2013

2×229 Posts
Default

Continue right here?

I happen to know that the ecm and factor commands is about factorization.

But you may find the isprime command being included in Yafu as well.

Is this command also based on the factorization algorithm, or is it rather based on LLR?

Software like WinPFGW is doing the similar thing by means of the LLR algorithm, which by some people may be regarded as an "approximation" to a given problem.

The question becomes then. Is it all about the number being processsed (including its possible size) and also what kind of computer that is being used? Also the question about which kinds of software (including version numbers) that are being used for a given task.

Is it more likely that a PRP5463 or PRP11943 is more likely to be accepted as being such a number using either Yafu or WinPFGW? Of course you should not able to factorize a 351,639 digit number like (2^1168183-1)/54763676838381762583.

http://donovanjohnson.com/mersenne.html

It took me 5 minutes to locate this number despite not having it here locally. You do not need a paper-based map or dictionary anymore. You are able to find almost everything you want with your PC alone.

I am also having a look at similar numbers like 7333*2^138560+1 (both with -1 and +1) that are roughly the same size.

According to http://www.factordb.com there are other numbers still listed as "U" being of similar size as this number.

So the conclusion may be that this is still an open question lacking a finite answer.

Last fiddled with by storflyt32 on 2014-10-20 at 16:01
storflyt32 is offline   Reply With Quote
Old 2014-10-20, 17:22   #13
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

67728 Posts
Default

You really should not be using yafu for primality or even prp checks of numbers this large.

However there is something interesting here:

Code:
int r;
mpz_t a;
mpz_init(a);
mpz_set_ui(a, 1);
mpz_mul_2exp(a, a, 138560);
mpz_mul_ui(a, a, 7333);
mpz_add_ui(a, a, 1);
printf("testing ...%lu\n", mpz_tdiv_ui(a, 1000000000));
r = mpz_probab_prime_p(a, 1);
printf("result is %d\n", r);
Linking with gmp 5.1.1 I get:
Code:
testing ...112555009
result is 0
Linking with gmp 4.3.2 I get:
Code:
testing ...112555009
result is 1
Bug in gmp 5.1.1?
bsquared is offline   Reply With Quote
Old 2014-10-20, 18:11   #14
storflyt32
 
Feb 2013

2×229 Posts
Default

Good post there, Batalov!
storflyt32 is offline   Reply With Quote
Old 2014-10-20, 18:23   #15
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×1,789 Posts
Default

Ok, after more checking I guess it's just yafu's use of gmp-5.1.1 that is messed up somehow. After remaking gmp-5.1.1 everything worked fine (result returned PRP).
bsquared is offline   Reply With Quote
Old 2014-10-20, 18:31   #16
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,393 Posts
Default

Ah. I was just about to ask if it fails for smaller inputs... Works fine here with 6.0.0.a ...
Code:
#include <stdio.h>
#include <gmp.h>

main()
{
int r;
int i, n[5] = {5774, 7932, 21704, 24976, 138560};
mpz_t a;
mpz_init(a);
for(i=0;i<5;i++) {
mpz_set_ui(a, 1);
mpz_mul_2exp(a, a, n[i]);
mpz_mul_ui(a, a, 7333);
mpz_add_ui(a, a, 1);
printf("testing 7333*2^%d+1 [...%lu]\n", n[i], mpz_tdiv_ui(a, 1000000000));
r = mpz_probab_prime_p(a, 1);
printf("result is %d\n", r);
}
}
Batalov is offline   Reply With Quote
Old 2014-10-20, 20:02   #17
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

C6A16 Posts
Default

With he mpz_probab_prime_p function you need a much bigger number than 1 as the second parameter for a big number like: 7333*2138560+1.

Code:
int mpz_probab_prime_p (const mpz t n, int reps) [Function]
Determine whether n is prime. Return 2 if n is definitely prime, return 1 if n is probably
prime (without being certain), or return 0 if n is definitely composite.
This function does some trial divisions, then some Miller-Rabin probabilistic primality tests.
The argument reps controls how many such tests are done; a higher value will reduce the
chances of a composite being returned as “probably prime”. 25 is a reasonable number; a
composite number will then be identified as a prime with a probability of less than 2−50
.
Miller-Rabin and similar tests can be more properly called compositeness tests. Numbers
which fail are known to be composite but those which pass might be prime or might be
composite. Only a few composites pass, hence those which pass are considered probably
prime.
Here is Thomas R. Nicely's page on the mpz_probab_prime_p pseudoprimes in earlier versions of GMP. They seem to change the bases a bit for the Miller-Rabin tests between versions, so that is probably why you get different results in different versions.
http://www.trnicely.net/misc/mpzspsp.html

Last fiddled with by ATH on 2014-10-20 at 20:07
ATH is offline   Reply With Quote
Old 2014-10-20, 20:21   #18
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

101010110011002 Posts
Default

Quote:
Originally Posted by ATH View Post
With he mpz_probab_prime_p function you need a much bigger number than 1 as the second parameter for a big number like: 7333*2138560+1.

Code:
int mpz_probab_prime_p (const mpz t n, int reps) [Function]
Determine whether n is prime. Return 2 if n is definitely prime, return 1 if n is probably
prime (without being certain), or return 0 if n is definitely composite.
This function does some trial divisions, then some Miller-Rabin probabilistic primality tests.
The argument reps controls how many such tests are done; a higher value will reduce the
chances of a composite being returned as “probably prime”. 25 is a reasonable number; a
composite number will then be identified as a prime with a probability of less than 2−50
.
Miller-Rabin and similar tests can be more properly called compositeness tests. Numbers
which fail are known to be composite but those which pass might be prime or might be
composite. Only a few composites pass, hence those which pass are considered probably
prime.
Here is Thomas R. Nicely's page on the mpz_probab_prime_p pseudoprimes in earlier versions of GMP. They seem to change the bases a bit for the Miller-Rabin tests between versions, so that is probably why you get different results in different versions.
http://www.trnicely.net/misc/mpzspsp.html
I suggest that 2 is "much bigger" than 1 for almost all purposes.

To see why, read up on the likelihood of the M-R test being mistaken for randomly chosen bases and randomly chosen numbers to test. If you chose the test number with malicious aforethought then, indeed, 25 tests may be appropriate. Such numbers are vanishingly rare.

Paul
xilman is offline   Reply With Quote
Old 2014-10-20, 20:23   #19
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,393 Posts
Default

This function (let's say called with 25 trials), of course, depending on the changing implementation can return a different (internal) chain of 1s, and then finally a 0 (which it will return) -- but only for a composite input. What it cannot do is return a 0 for a prime input. (which is what B.B. properly flagged as a bug. Then, it turn, even if the function is coded correctly, there are ways to miscompile, and that is what appears to be what he later diagnosed.)

For this input, one would expect an infinite row of "1"s returned (probable prime); the reason why Ben coded (...,1) was that it is quite slow for even a single M.-R. test. (~15 minutes on a fast core; pfgw takes 15 s, because it plain GMP uses a general version of multiplication and pfgw, a special fast one)
Batalov is offline   Reply With Quote
Old 2014-10-21, 23:29   #20
storflyt32
 
Feb 2013

2×229 Posts
Default

Please see this thread.

http://mersenneforum.org/showthread.php?t=14249

If you do not mind, often a smaller number may be harder to factorize than a larger number.

The reason for this is that the factors are more equal in size to each other.

Knowing that a P8 like 36085879 is a factor of 2^333-1 is no problem, but factorizing a composite number like
293155093804870332610909957481872064551757337569254797370666783 is a little bit harder to do.

Please have me excused, but those numbers ending with -1 in the syntax definitely are a little more easy to be dealing with.

The biggest prime number that is currently known is a Mersenne prime.

Compare with the similar or corresponding Fermat search.

Right now, the largest known Fermat prime is 475856^524288+1 which is a quite bit smaller number than Mersenne48 (or M48).
So, before I started to get a hand on this stuff, I was wondering why such a prime number like the one mentioned above
is that little bit larger than the largest known fermat "factor".

http://factordb.com/index.php?query=2%5E2048%2B1

The P564 at the right in that listing.

What is the possible relationship between these two numbers?

Is it possible to assume that a number containing some 2,976,633 digits itself might be a factor of some other even larger number (which then becomes a composite one)?

No reason to doubt why doing this kind of stuff is supposed to be a little hard to do at times.

Because you are unable to factorize such a number (like the remainder of 2^4096+1 or 2^8192+1), you do not know what the
factors are. The question becomes - is it possible to relate a specific number (factor) to a particular set of prime types?

Looking at it, I get the feeling that there may be a correspondence or relationship between a Genefer number and a rep-digit number.

Your opinion on this, please.

Thanks!
storflyt32 is offline   Reply With Quote
Old 2014-10-21, 23:43   #21
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·1,291 Posts
Default

Quote:
Originally Posted by storflyt32 View Post
Knowing that a P8 like 36085879 is a factor of 2^333-1 is no problem, but factorizing a composite number like
293155093804870332610909957481872064551757337569254797370666783 is a little bit harder to do.
Code:
? factor(293155093804870332610909957481872064551757337569254797370666783)

[6951431036147505831119048893 1]

[42171905652298228542447931081982731 1]
paulunderwood is offline   Reply With Quote
Old 2014-10-22, 00:15   #22
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,393 Posts
Default

Quote:
Originally Posted by storflyt32 View Post
... numbers ending with -1 in the syntax definitely are a little more easy to be dealing with.

The biggest prime number that is currently known is a Mersenne prime.

Compare with the similar or corresponding Fermat search.

Right now, the largest known Fermat prime is 475856^524288+1 which is a quite bit smaller number than Mersenne48 (or M48).
So, before I started to get a hand on this stuff, I was wondering why such a prime number like the one mentioned above
is that little bit larger than the largest known fermat "factor".
You may want to read this introduction: http://primes.utm.edu/prove/ (the whole set of linked pages, not just that page ;-)
It will become clear why most known giant primes are either ...-1 or ...+1.

Quote:
Originally Posted by storflyt32 View Post
...Because you are unable to factorize such a number (like the remainder of 2^4096+1 or 2^8192+1), you do not know what the
factors are. The question becomes - is it possible to relate a specific number (factor) to a particular set of prime types?
The b^n+-1 numbers do have very special factors (of special restricted form). This is true for Mersennes and Fermats, but also true for generalized Fermats, and (further generalized) cyclotomic numbers.

Read, the read some more, and you questions will be answered. Don't expect someone to stand by and be ready to answer your (so far, pretty basic) questions. "Give a man a fish... Teach a man to fish..." that sort of thing.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Composite being Prime kruoli FactorDB 5 2018-02-16 16:54
How can I prove this PRP prime? siegert81 Math 2 2014-11-19 10:24
How do I prove a 4000 digit number is prime?? VJS Lounge 4 2005-05-09 20:56
How do you prove a number is prime? Alien Math 12 2004-01-07 11:36
why not stop when composite is prove? mdjvz Software 4 2003-09-28 17:13

All times are UTC. The time now is 12:05.


Mon Oct 25 12:05:03 UTC 2021 up 94 days, 6:34, 0 users, load averages: 1.59, 2.00, 1.96

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