T.R | Title | User | Personal Name | Date | Lines |
---|
1017.1 | | AITG::DERAMO | Daniel V. {AITG,ZFC}:: D'Eramo | Tue Jan 24 1989 21:50 | 19 |
| If G is a generator for the prime p, then
p-1
G = 1 (mod p)
and
(p-1)/q
G not= 1 (mod p) for every prime q dividing p-1
Conversely, if both conditions are satisfied then G is a
generator.
Actually, the first condition is true for every G not
divisible by p.
Is there a similar test for finite fields of size a power of p?
Dan
|
1017.2 | racking memory | HERON::BUCHANAN | Andrew @vbo/dtn8285805/ARES,HERON | Tue Jan 24 1989 21:57 | 66 |
1017.3 | details | HERON::BUCHANAN | Andrew @vbo/dtn8285805/ARES,HERON | Tue Jan 24 1989 22:08 | 15 |
| > Is there a similar test for finite fields of size a power of p?
Yes, because all finite fields have cyclic multiplicative group.
(p-1)/q
G <> I in GF(p^a) for every prime q dividing (p^a)-1
Conversely, if condition is satisfied then G is a generator.
(Once again, Deramo and I input replies at the same time. Twin hounds
of truth, our flanks brush as we urgently quest the quarry.)
Time for bed, yawn.
Andrew
|
1017.4 | thanks | NETMAN::STELL | Doug Stell, DTN226-5245, LKG1-1/C6, Pole A7 | Wed Jan 25 1989 19:46 | 18 |
| Thanks for the replies. I ran some examples and the algorithm in .1
worked just fine. Of course, the numbers were small enough that I could
factor p-1 by inspection.
Given that the prime is probably quite large (255-1000 bits, depending
on the location [U.S. vs. elsewhere] and export situation), does any one
have any good ideas on how to avoid factoring p-1? How about building
the modulus from the product of some primes plus 1 and testing it for
primality?
Since one of you asked what I wanted this for, I am considering using
the Diffie-Hellman public key exchange for authentication on a large
network application within DEC. The request is really work-related, but
D-H is only a candidate being considered at this point. D-H is based on
exponentiation of a generator modulo a prime and none of the literature
I could find gave me a good method for finding the generator.
thanks again, doug
|
1017.5 | Model for GF(p^a), a>1 ?? | HPSCAD::HERMAN | | Wed Jan 25 1989 20:08 | 24 |
|
> Is there a similar test for finite fields of size a power of p?
>> Yes, because all finite fields have cyclic multiplicative group.
(p-1)/q
>> G <> I in GF(p^a) for every prime q dividing (p^a)-1
>> Conversely, if condition is satisfied then G is a generator.
The finite field GF(p) containing p elements, p prime, has a simple model
as modulo arithmetic with modulus p. Is there a simple model for the
fields GF(p^a) the field with p^a elements with (a > 1) ? In otherwords
how would one specify an element G of GF(p^a) so that we could ask if
it was a generator under multiplication of the non-zero elements?
Note that modulo arithmetic with modulus p^a fails to be such a
model since
p * p^(a-1) = 0 (mod p^a)
i.e., p^(a-1) is a zero divisor.
-Franklin
|
1017.6 | | AITG::DERAMO | Daniel V. {AITG,ZFC}:: D'Eramo | Wed Jan 25 1989 22:15 | 44 |
| re .4
The RSA cryptographic system involves generating two large
primes p and q such that their product pq is difficult to
factor [to someone knowing pq but not p or q]. There is a
discussion in Knuth's books on how to generate such large
primes [The Art of Computer Programming, Vol. 2].
The method he suggests for a prime p of approximately 120
digits is:
select a truly random P0 between 10^80 and 10^81
search for the first prime P1 > P0
select a truly random P2 between 10^39 and 10^40
let p be the first prime of the form K * P1 + 1
for K >= P2
[note that P0, P2, and K are not required to be
primes in the above]
The prime p is about 120 digits, but by the construction you
already know the (about 80 digit) prime factor P1 of p-1.
It would still be necessary to factor K, but it has only
about 1/3 as many digits as p does.
I don't know if your application requires special
properties of p, for example that p-1 be difficult to
factor.
re .5
There would be an element "x" of the field (of p^a elements,
a > 1) such that each element of the field could be
represented by a different polynomial in x with degree < a
and coefficients the integers modulo p.
For example the field with 125 elements would have the 125
elements a + bx + cx^2 where a,b,c vary through {0,1,2,3,4}
and where x represents a root of a third degree polynomial
with coefficients {0,1,2,3,4} which cannot be factored over
the polynomials with coefficients {0,1,2,3,4}. One
possibility is x^3 + x + 1 = 0.
Dan
|