mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-06-25, 23:20   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default P-1

Just need some clarification,

Is this quote wrong.

"There is an enhancement to Pollard's algorithm called stage 2 that uses a second bound, B2. Stage 2 will find the factor q if k has just one factor between B1 and B2 and all remaining factors are below B1."

Taken from

http://www.mersenne.org/math.htm

Let me know!

Thanks,
Citrix
Citrix is offline   Reply With Quote
Old 2004-06-26, 03:12   #2
Axel Fox
 
Axel Fox's Avatar
 
May 2003

1408 Posts
Default

Nope, that sounds about right.

First stage only uses B1 and all factors of k have to be below B1.
Stage two is a little more general and allows for 1 of the factors of k to be above B1, but still below a second bound (B2).

Greets,
Axel Fox.
Axel Fox is offline   Reply With Quote
Old 2004-06-26, 03:38   #3
Citrix
 
Citrix's Avatar
 
Jun 2003

32×52×7 Posts
Default

Why can't there be 2 k's between b1 and b2? I think there can be 2 or more k's.

Citrix

Last fiddled with by Citrix on 2004-06-26 at 03:39
Citrix is offline   Reply With Quote
Old 2004-06-26, 03:58   #4
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

Quote:
Originally Posted by Citrix
Why can't there be 2 k's between b1 and b2? I think there can be 2 or more k's.

146420587 |79309*2^513-1

Found this uisng a program I wrote.
b1=25 and b2=1000.

I think this prooves my point.

Citrix

Last fiddled with by Citrix on 2004-06-26 at 03:59
Citrix is offline   Reply With Quote
Old 2004-06-26, 04:51   #5
axn
 
axn's Avatar
 
Jun 2003

4,721 Posts
Default

Can you post your program here?
axn is online now   Reply With Quote
Old 2004-06-26, 05:01   #6
Citrix
 
Citrix's Avatar
 
Jun 2003

157510 Posts
Default

Here you go.
It is very basic.
The routines are primitive etc.
Don't try very large numbers.


The file is 183 KB, it won't let me upload it. If you PM me your email, I can send it to you or better yet I can test and print the results for you.

Citrix
Citrix is offline   Reply With Quote
Old 2004-06-26, 06:49   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

There are at least three effects how P-1 can occasionally find factors that are not B1,B2 smooth. Say p-1 has two factors >B1, r and s.

- The starting element of P-1 could already be an r-th or s-th power (mod p). Then there is no need to exponentiate by r for P-1 to find p. The probability of a random residue being an r-th power (mod p) is 1/r if r|p-1 so this wont happen often for large r. For example, the smallest starting values that are a 127-th power (mod 146420587) are 89, 149, 219, 554...

- The implementation of P-1 might exponentiate by N-1 at the start of stage 1. This is useful if there is some k that divides p-1 for every prime factor p of N because is includes k as a stage 1 exponent, without having to know what the actual value of k is. But this is not what happened here, neither 127 nor 379 divide 79309*2^513-2.

- The r and s may be included by the Brent-Suyama extension. If t is the order of the end-of-stage-1 residue, the factor p will be found if t|f(l)-f(m). Here f() is the Brent-Suyama function (usually just a power) and l and m are usually chosen so that all primes >B1, <=B2 are included. It's possible that a composite t divides one such value, but is again not too likely to happen. Whether that's why the factor was found requires knowing which function f() the implenentation uses and how it generates the l and m values.

Alex

Last fiddled with by akruppa on 2004-06-26 at 06:50
akruppa is offline   Reply With Quote
Old 2004-06-26, 06:53   #8
Citrix
 
Citrix's Avatar
 
Jun 2003

32×52×7 Posts
Default

My program used base 3 to start with.

Also p-1= 2 x 3 ^ 2 x 13 ^ 2 x 127 x 379

All factors found by my program irrespective of the base fall in the same category.

Citrix

Last fiddled with by Citrix on 2004-06-26 at 06:55
Citrix is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 14:28.

Fri Oct 30 14:28:10 UTC 2020 up 50 days, 11:39, 1 user, load averages: 2.39, 2.12, 2.00

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.