Other Bases?

[Christenson]

Originally Posted by R.D. Silverman

I never called you a weak student. But the very very many elementary
mispronouncements that you continue to make, and the ignorance you
show (even about very elementary aspects of this subject) suggests that you are a lazy student; unwilling to do the required reading.

I did get as far as MPQS, and got bogged down with SNFS and GNFS.

I am working on the required reading, but have come to the realisation that there are parts of comp sci (starting with Turing Machines) that were excluded from my engineering comp sci education. You have to realize it's hard work and it doesn't happen overnight, especially as I do have a full-time job amongst a bunch of engineers who don't know what a Mersenne prime is in the first place, have long since forgotton what a Laplace transform is, and wouldn't know the difference between the Eiger and an Eigenvalue.

I'm also debating whether taking on a project here; I have one that has to finish first, and the coding involved is temporarily soaking up all my available math bandwidth.

And while I'm at it, do let me know if I have correctly shown that the number I was asking about is divisible by 40. You will get much further if you encourage and reward correctness, just ask BF Skinner!

[Christenson]

Originally Posted by R.D. Silverman

I never called you a weak student. But the very very many elementary
mispronouncements that you continue to make, and the ignorance you
show (even about very elementary aspects of this subject) suggests that you are a lazy student; unwilling to do the required reading.

If you'd told me the modular exponentiation was as easy as I found it when I sat down and looked at it, I'd have looked closer sooner!

Wblipp:
Current mfaktc assignments are of the form
factor=43112609,72,73
which means:
factor 2^43112609-1 with trial factors between 2^72 and 2^73.

What's the best representation for the assignments you would want TF'ed, in general form?

[wblipp]

Originally Posted by Christenson

Current mfaktc assignments are of the form
factor=43112609,72,73
which means:
factor 2^43112609-1 with trial factors between 2^72 and 2^73.

What's the best representation for the assignments you would want TF'ed, in general form?

I'd be happy with

factor=base,exponent,lowlim,hilim

meaning: trial factor base^exponent-1 with primes of the form k*exponent+1 between lowlim and hilim.


I'd be ecstatic with

factor=base,exponent,multiplier,lowlim,hilim

meaning: trial factor base^(exponent*multiplier)-1 with primes of the form k*exponent+1

The ecstatic form makes it easy to trial factor a^n+1 by making multiplier=2. It also allow me to simultaneously search all the large algebraic factors of 719^(2^2 * 3 * 183925013)-1, one of the target groups from

http://oddperfect.org/FermatQuotients3.html

I have no particular preference for how represent lowlim and hilim, If powers of two are still easy, that has the advantage of familiarity. If there is something that much easier to implement and not too hard to understand, that would be fine, too.

William

[Christenson]

I'm wondering if we don't want to talk about a set of multipliers here, rather than a single multiplier, with the single multiplier being a special case of the set. After all, if I calculate 719^(large prime #) mod factor candidate, then squaring or cubing the result, mod factor candidate, is significantly easier than re-performing that large exponentiation, which, will on average, have two dozen squarings and a dozen multiplies by the base.

[science_man_88]

http://www.mersenneforum.org/showpos...postcount=2269

gives PARI code you can modify for GPU. Yes the TF allows all bases the MTF code is just base 2 but can be transformed into a code for all bases.

[Ken_g6]

Originally Posted by Christenson

I'm wondering if we don't want to talk about a set of multipliers here, rather than a single multiplier, with the single multiplier being a special case of the set. After all, if I calculate 719^(large prime #) mod factor candidate, then squaring or cubing the result, mod factor candidate, is significantly easier than re-performing that large exponentiation, which, will on average, have two dozen squarings and a dozen multiplies by the base.

I've wondered for a long time why TF doesn't do something like this, or even better a fixed-K sieve, like srsieve, where K = 1. I guess I figured it's because srsieve is limited to ~61 bits.

[LiquidNitrogen]

I was wondering if there would be any "ideal bases" that would find primes with as few k's and as few n's as possible, but with a fair number of +/- constants after.

Maybe bases of the form:

1001
10001
100001
10000 .... 00001

So instead of varying the base for a trial run, fix the base, have a few "n's", more k's, and a boatload of constants.

1000000000001^101 = 1000000000101000000005050000000166650000004082925000079208745001267339920017199613200202095455102088319702719212541264998940114101232050855758460963550957197485177420325414028911439100404799285502021331095676088416183742868800643345599775151475315716866271985731991536958006272477324491587179583856827926513500592331682134232579237482724796258175554928347429243705759667435386284646565561783499781088436421274567683484763110034583156211880651084039705547277573596329704668260931674800987143837558770872396880395834070399710309414813490464221426099706416891571300436092852676414058203975930443434784401657764255585676928675700936563632656314818056403647636947150112778481979034466162277360787229204891362831139710078397045966918388927493954592422300818497143405081842346660487844922705804890338008781881274489066410808378334402491151807644536641030814549929237444717786503985982357609317621631880828590342131116476187226483491441690568696242366219581466610133513343184956453742237790345675933406095501985615649100397100815414027363537485177130960963550907092050855750458940114100059212541264842088319702700202095455100017199613200001267339920000079208745000004082925000000166650000000005050000000000101000000000001

k*(b^p)+c

k = 2
b = 1000000000001
p = 101

Check constants in the range of +1 to +5001

(the next prime would be at +568 for the large number shown above)

k = 3
b = 1000000000001
p = 101

Check constants in the range of +1 to +5001

etc.

With a clever combination of b and p I would make the SWAG that a prime would be "in the neighborhood" and checking a few constants might pay high dividends.

[Christenson]

Originally Posted by Ken_g6

I've wondered for a long time why TF doesn't do something like this, or even better a fixed-K sieve, like srsieve, where K = 1. I guess I figured it's because srsieve is limited to ~61 bits.

I suspect the answer has to do with the limited amount of time a developer such as myself has to work on it.

Keep talking...remember that mfaktc is going to run out of effective work fairly soon and should be looking for new targets and improved methods.

[science_man_88]

Originally Posted by Christenson

I suspect the answer has to do with the limited amount of time a developer such as myself has to work on it.

Keep talking...remember that mfaktc is going to run out of effective work fairly soon and should be looking for new targets and improved methods.

I'm supposed to be preparing to move as far as I know but I also don't have the skill needed to do the programming.

[wblipp]

Originally Posted by Christenson

I'm wondering if we don't want to talk about a set of multipliers here, rather than a single multiplier, with the single multiplier being a special case of the set. After all, if I calculate 719^(large prime #) mod factor candidate, then squaring or cubing the result, mod factor candidate, is significantly easier than re-performing that large exponentiation, which, will on average, have two dozen squarings and a dozen multiplies by the base.

No, that puts the complexity in the wrong place. When the searcher is interested in a set of multipliers, he enters the GCD of his set. Any divisor for any of the set will also divide this number. It's a simple matter to determine which member of the set as a post processing step outside of the trial factor code. In the early days of the ElevenSmooth project we used this method on the entire composite with Prime95, and then figured out the algebraic factor for each divisor we found.

William

[Christenson]

Originally Posted by wblipp

No, that puts the complexity in the wrong place. When the searcher is interested in a set of multipliers, he enters the GCD of his set. Any divisor for any of the set will also divide this number. It's a simple matter to determine which member of the set as a post processing step outside of the trial factor code. In the early days of the ElevenSmooth project we used this method on the entire composite with Prime95, and then figured out the algebraic factor for each divisor we found.

William

I'm confused...I think you are saying that:
if TF factors 41^P-1, then it also factors 41^(K*P)-1, where K and P are positive integers and P is usually prime...since 41^P mod TF =1, and (41^P)^k mod TF = 1^k =1.

therefore, we should be TF'ing over some large set of TFs by calculating 41^P mod TF, and then reporting if 41 ^P mod TF is a reasonably small root of unity (up to some bound) mod TF.

Or can you give me a slightly more concrete example?