Re: Possible test for divisor of Phi(N)
From: Ralfe Cookson (ralfe.cookson_at_ngc.com)
Date: 08/08/03
- Next message: George Joseph: "Does Barrett have any restrictions?"
- Previous message: Wei Dai: "Re: License questions"
- In reply to: Mok-Kong Shen: "Re: Possible test for divisor of Phi(N)"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 7 Aug 2003 20:55:24 -0700
Mok-Kong Shen <mok-kong.shen@t-online.de> wrote in message news:<3F32D843.1724F9E@t-online.de>...
> Some dumb questions: (1) In the first paragraph above
> you want to find those rows that have fewer unique values,
> if I understand correctly. Why don't you just compute,
> for each randomly chosen row, from a sample the percentage
> of unique values in that row and use that directly to see
> which row is more likely to have fewer values and instead
> have to employ the idea of the second paragraph? (2) It
> is not apparent/clear how the criterion of the second
> paragraph, namely the existence of certain 'abnormal'
> distribution of prime factors of the values of a row,
> is related to the lower number (count) of unique values
> of the row. Could you explain a little bit what you have
> in mind with respect to that? (3) What do you mean by an
> 'abnormal' vs a 'normal' distribution of the prime factors
> of the values of a row? Do you take that distribution
> from all values computed or only from the unique ones
> out of all values computed in a row? Thanks.
>
> M. K. Shen
Thank you for your interest in my post. The questions are not dumb, and perhaps
the algorithm is.
Since in general the number N would be very large, I would not expect to
find any repeats mod N in the relatively small samples of residues that I
generated and then factored. Therefore every residue would be unique. Repeats
mod N would show up only after taking a ridiculously large number of residues.
What I was hoping for was that since the rows that correspond to exponent X
= a divisor of phi(N) would be missing a lot of the residues, then maybe this
might be detectable some how, even if one took only a small sample of the
residues in that row.
To test this idea under ideal cases, I did some very crude experiments on very
small numbers and found that it seems to be true. Some primes were missing
from the factorizations of the residues. In an earlier post I listed a crude
UBASIC program that demostrates this. It is ridiculous for any practical
purposes as it test all N-1 residues corresponding to columns for A = 1 to
N - 1, (and due to a bug, more, such that modulo N they repeat wasting time)
and it completely factors the residues over a "factor base" of all primes up
to about (N-1)/2. It was only to test the idea in an ideal, but totatlly
impractical way, but it seems to indicate the idea may have some validity.
By a "normal" distribution of prime factors, I mean the distribution of primes
that one would expect from a random set of integers. That is on average every
Pth integer would be expected to be a multiple of some prime P. Since for the
rows X=1 all the residues from 1 to N-1 are present and in sequential order,
I would expect the distribution of the prime factors in this row to be: every
2nd residue is a multiple of 2, every 3rd is a multiple of 3, every 4th is a
multipe of 2^2, etc. The rows that correspond to X that contain no factors of
phi(N), i.e. gcd(X, phi(N)) = 1, also have all the residues from 1 to N-1, but
in a scrambled up order. So I was hoping if I took some random subset of these
I would still detect the "normal" distribution of primes in their
factorizations. However for the rows where X is such that gcd(X, phi(N))>1,
the larger the better, there are a less unique residues, so perhaps some primes
from the missing residues would show up less, and to compensate some other
primes may show up more. By random chance one would not expect this to be the
case. If one random selects a fraction of a bunch of integers, I would still
expect them to have a normal distribution of prime factors, provided the
original set did. But then I do not believe that this is a case of random
chance, as something about X being a factor of phi(N) may affect not just what
residues show up, but also what primes are in them. I do not have the math
ability to explain why this may be true. It was just a hunch.
My simple experimental UBASIC programs seemed to indicate it may be true.
I found some primes did not show up at all, and in my first UBASIC
program in the earlier post, this is all I used to "score" each trial divisor.
For these small numbers I was able to use as all primes up to < N-1/2 to factor
all N-1 residues and it did indicate the distribution of the primes in the
factorizations of the residues is different for rows where X is a divsor of
phi(N).
Of course this is impractical as an algorithm. One must use much less
factors in the factor base, and use a much smaller sample of residues.
So I did some experiments with larger integers, and it still seems to work,
sort of, depending on how big the factor base is and how many samples I take,
and what samples I take and so on. There is a lot of room for improvement here.
I factor all the residues that appear and then count the primes.
I hope that answers your questions. If not, perhaps the ideas may be more
clear from my UBASIC promgrams I posted.
- Next message: George Joseph: "Does Barrett have any restrictions?"
- Previous message: Wei Dai: "Re: License questions"
- In reply to: Mok-Kong Shen: "Re: Possible test for divisor of Phi(N)"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
