Probabilistic optimization of P-1 efforsts?

[ramshanker]

Hi all,
Lately I have been banging my head over alternate implementation of P-1 test. Having checked quite a few factors, I can't recall seeing any high (say >10) power for factors of "k" in 2kp.

Smaller digits seem to have sometimes up to 7th or 8th power, specially 2,3 & 5. However higher factors rarely go up to 3rd power.

So would it not be justified, in a probabilistic way to use only fewer powers while calculating E? Notation as in http://www.mersenne.org/various/math.php


I know you can't guarantee that you undertook P-1 test on an exponent with reduction in powers, but than this could be backed by probabilistic distribution of data based on 10s of million of known factors. :)


While we are at it, am I allowed to scrap primenet server for known factors / factoring status?

I am yet to understand why B2 bound work.

[R.D. Silverman]

Originally Posted by ramshanker

Hi all,
Lately I have been banging my head over alternate implementation of P-1 test. Having checked quite a few factors, I can't recall seeing any high (say >10) power for factors of "k" in 2kp.

Smaller digits seem to have sometimes up to 7th or 8th power, specially 2,3 & 5. However higher factors rarely go up to 3rd power.

So would it not be justified, in a probabilistic way to use only fewer powers while calculating E?

The probability that an integer N is divisible by p^k, is very nearly 1/p^k. SUM from p=2 to oo of 1/p^k converges
very rapidly. We do not expect high powers of primes to appear very often.

The phrase "justified, in a probabilistic way" is meaningless without an objective function.
What objective function do you propose? What optimization do you propose?

There is always a possibility that we may fail to find a factor p|N when p-1 is divisible by a high power.
This is the nature of the algorithm. The same applies for ECM.

It is not necessary to pre-calculate E to run the algorithm.

I know you can't guarantee that you undertook P-1 test on an exponent with reduction in powers, but than this could be backed by probabilistic distribution of data based on 10s of million of known factors. :)

What is the antecedent of the word "this" in your last sentence? What do you mean by "backed"?
What are you measuring? We don't need empirical data. The distribution of prime factors of p-1
is well known theoretically.

While we are at it, am I allowed to scrap primenet server for known factors / factoring status?

I am yet to understand why B2 bound work.

What do you mean by "scrap primenet"? Running P-1 does not require adherence to any organized effort.

As for understanding B2, one can only read descriptions of the algorithm. I can help, but without
knowing what it is that you don't understand, I can't give any specific information.

[R.D. Silverman]

Originally Posted by R.D. Silverman

The probability that an integer N is divisible by p^k, is very nearly 1/p^k. SUM from p=2 to oo of 1/p^k converges
very rapidly.

I forgot to add: for k > 1

[fivemack]

Originally Posted by ramshanker

Hi all,
Lately I have been banging my head over alternate implementation of P-1 test. Having checked quite a few factors, I can't recall seeing any high (say >10) power for factors of "k" in 2kp.

Smaller digits seem to have sometimes up to 7th or 8th power, specially 2,3 & 5. However higher factors rarely go up to 3rd power.

So would it not be justified, in a probabilistic way to use only fewer powers while calculating E? Notation as in http://www.mersenne.org/various/math.php

I believe that is what's done; if you have B1=10^6 you will put in 2^19 (largest power of two less than 10^6), 3^12 (largest power of three less than 10^6), ..., 97^3, 101^2, ..., 997^2, 1009 ...

[ramshanker]

Originally Posted by R.D. Silverman

What do you mean by "scrap primenet"? Running P-1 does not require adherence to any organized effort.

Downloading all the known factors stored by primenet server (from mersenne.org web pages) by an automated script.

Originally Posted by R.D. Silverman

The distribution of prime factors of p-1 is well known theoretically.

Ok. I will study more on that one. Thanks.

[chris2be8]

Originally Posted by R.D. Silverman

What do you mean by "scrap primenet"?

He probably meant "scrape primenet". If so that's a question for George to answer (it probably depends how much load it'll put on the server).

Chris

[R.D. Silverman]

Originally Posted by ramshanker

Downloading all the known factors stored by primenet server (from mersenne.org web pages) by an automated script.

This answer does not say what you mean by "scrap".
Nor does it explain why one needs to involve primenet. It is not needed to run P-1.
It might be needed for some particular project, but your post gave no indication of that.

It is also unclear as to why one needs to download known factors.

[ramshanker]

Originally Posted by R.D. Silverman

This answer does not say what you mean by "scrap".
Nor does it explain why one needs to involve primenet. It is not needed to run P-1.
It might be needed for some particular project, but your post gave no indication of that.

It is also unclear as to why one needs to download known factors.

Pardon my english. https://en.wikipedia.org/wiki/Web_scraping

I didn't know distribution of factors of P-1 is well known THEORETICALLY.

It can (?) be done numerically in following way. Let's say we collect 1 million known factors of mersenne number. Now if highest power of 2 in factors of (2kp) is let's say 7 (picking just random value here, it could be some other value). With this observation, we could skip to compute only a^(2^7) instead of a^(log B1 base 2).

It would introduce a "chance" to missing some factors, hence I said "probilistic", but hey we are skipping quite a few cycles.

[R.D. Silverman]

Originally Posted by ramshanker

Pardon my english. https://en.wikipedia.org/wiki/Web_scraping

I didn't know distribution of factors of P-1 is well known THEORETICALLY.

It can (?) be done numerically in following way.

What is "it"??? i.e. What can be done numerically? I asked before and you did
not answer: What problem are you solving? What optimization are you doing?

Let's say we collect 1 million known factors of mersenne number. Now if highest power of 2 in factors of (2kp) is let's say 7 (picking just random value here, it could be some other value). With this observation, we could skip to compute only a^(2^7) instead of a^(log B1 base 2).

You still fail to state your OBJECTIVE. And collecting known factors is irrelevant.
You say "could skip to only a^(2^7)". We could also sing hyms, paint pictures,
jump on a trampoline, run a marathon, or only ' skip to a^2^3'. We COULD do anything we want.
But unless you state an OBJECTIVE, saying "we could ......." is meaningless.

It would introduce a "chance" to missing some factors, hence I said "probilistic", but hey we are skipping quite a few cycles.

You could skip even more cycles by not using prime powers at all: just use p^1.
Once again, what is your OBJECTIVE?????

Your statements so far are meaningless and vacuous.

[ramshanker]

OBJECTIVE: Reduce the number of computation required to perform P-1 factorization.

HOW: By reducing the power-to-raise during modular exponentiation phase.

MATH: To establish distribution of factors (and hence upper limit on power of small factors) of P-1 by observing the trend among collected factors of other mersenne number. As you stated, it is well know theoretically.

Consider this exploration only a personal effort.

[R.D. Silverman]

Originally Posted by ramshanker

OBJECTIVE: Reduce the number of computation required to perform P-1 factorization.


HOW: By reducing the power-to-raise during modular exponentiation phase.

Reduce the power all the way to 1. This will save a lot of time.
Or even better: reduce the exponents to 0. This will save even more time.
There are many things one can do to reduce the computation. But they all
have a COST associated with them. I see no discussion of this cost in your
arguments. The cost is, of course, a reduction in the likelihood of finding a factor.
But unless you specify how the probability changes as a function of the reduction in time,
and unless you specify some objective for your probabilities, the discussion is meaningless.

One can, for example, reduce the time needed to ZERO. Do nothing. This gives
a zero probability of succeeding, but nothing in your statements places any kind
of constraint on what probability you are willing to accepy.

MATH: To establish distribution of factors (and hence upper limit on power of small factors) of P-1 by observing the trend among collected factors of other mersenne number.

This proposal is not mathematics. It is simply making an empirical observation.
And it will fail to "establish distribution of factors".
It is just mindless numerology.

Perhaps you might take a university level course on probability and statistics?
It will allow you to gain some understanding of what you are trying (in vain)
to propose.

You should also take at least a semester on optimization methods/operations research.

Would someone else weigh in here? I do not seem to be getting through.