Re: Elementary group theory: Proof of Fermat-Maas primality-test (was: correcting *** ...)

In my previous article, I listed three possible algorithms for
generating a primitive element modulo prime p, assuming
factorization of p-1 was known and used via the Fermat-Maas
algorithm to prove primality. Actually I later realized the first
of the three options, "Fullfledged triangulation Gaussian
elimination", has two variations:
-1a- Traditional trangularizing, working from left to right, not
caring if not-yet-processed columns get temporarily made worse.
-1b- Taking sufficient power of pivot ("side") row that no column is
*ever* made worse, so you don't have to work from left to right.

I went ahead and coded algorithm -1b- Saturday.

The algorithm works like this: Look for a row with the least number
of 1's that need conversion to X's. Once that is chosen, look for
another row that will be effective at converting the maximum number
of those few 1's in a single pivot. Thus the algorithm is designed
to start as close to the goal as possible and to move toward it as
fast as possible with each step.

Most of the time only one pivot is needed. Below are some examples
where at least two pivots were needed even with this algorithm:


pm1facs = (2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 5 5 7 7 11 11 13 13 17 23 23 29 43
67 281 997 13757 14683 19913)
Starting matrix:
((B 2 3 5 7 11 13 17 23 29 43 67 281 997 13757 14683 19913)
(2 1 1 X 1 X X X X X X X X X X X X)
(3 1 X 1 1 X X X X X X X X X X X X)
(5 1 1 X X X X X X X X X X X X X X)
(31 X 1 X X X X X X X 1 X X X X X X))
Mininum number of 1's in any row is 2, which occurs in 2 row(s):
((5 1 1 X X X X X X X X X X X X X X) (31 X 1 X X X X X X X 1 X X X X X X))
Selected main row:
(5 1 1 X X X X X X X X X X X X X X)
Least number of common 1's is 1, which occurs in 2 side row(s):
((3 1 X 1 1 X X X X X X X X X X X X) (31 X 1 X X X X X X X 1 X X X X X X))
Side row chosen:
(3 1 X 1 1 X X X X X X X X X X X X)
Factors in exponent:
(1 1 1 1 11 13 17 23 29 43 67 281 997 13757 14683 19913)
= 5264180342108344080155630327
Taking that side row to that power yields:
(3603730164531153722895318711271737489466 1 X 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
Multiplying main row by that, converted main row is now:
(18018650822655768614476593556358687447330 1 X X X X X X X X X X X X X X X)
Mininum number of 1's in any row is 1, which occurs in 1 row(s):
((18018650822655768614476593556358687447330 1 X X X X X X X X X X X X X X X))
Selected main row:
(18018650822655768614476593556358687447330 1 X X X X X X X X X X X X X X X)
Least number of common 1's is 0, which occurs in 1 side row(s):
((31 X 1 X X X X X X X 1 X X X X X X))
Side row chosen:
(31 X 1 X X X X X X X 1 X X X X X X)
Factors in exponent:
(1 1 5 7 11 13 17 23 29 1 67 281 997 13757 14683 19913)
= 4284797952878884716405745615
Taking that side row to that power yields:
(17987579322879611214229733769083110795292 X 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
Multiplying main row by that, converted main row is now:
(11456073748651916615672245336224879945935 X X X X X X X X X X X X X X X X)
Mininum number of 1's in any row is 0, which occurs in 1 row(s):
((11456073748651916615672245336224879945935 X X X X X X X X X X X X X X X X))
** Primitive element: b=11456073748651916615672245336224879945935
which required 2 pivot(s)


pm1facs = (2 2 2 3 3 3 5 5 7 7 11 13 17 29 887 1021 4729 5801 105359 472301
904219)
Starting matrix:
((B 2 3 5 7 11 13 17 29 887 1021 4729 5801 105359 472301 904219)
(2 1 1 1 X X X X X X X X X X X X)
(3 1 X 1 X X X X X X X X X X X X)
(5 1 1 X X X X X X X X X X X X X)
(19 X 1 X X X X 1 X X X X X X X X))
Mininum number of 1's in any row is 2, which occurs in 3 row(s):
((3 1 X 1 X X X X X X X X X X X X) (5 1 1 X X X X X X X X X X X X X)
(19 X 1 X X X X 1 X X X X X X X X))
Selected main row:
(5 1 1 X X X X X X X X X X X X X)
Least number of common 1's is 1, which occurs in 2 side row(s):
((3 1 X 1 X X X X X X X X X X X X) (19 X 1 X X X X 1 X X X X X X X X))
Side row chosen:
(3 1 X 1 X X X X X X X X X X X X)
Factors in exponent:
(1 1 1 7 11 13 17 29 887 1021 4729 5801 105359 472301 904219)
= 551653873086867079346822108768262599
Taking that side row to that power yields:
(14562014278943208168338516313208789287793 1 X 1 1 1 1 1 1 1 1 1 1 1 1 1)
Multiplying main row by that, converted main row is now:
(10252522186665314043762954431722967712362 1 X X X X X X X X X X X X X X)
Mininum number of 1's in any row is 1, which occurs in 1 row(s):
((10252522186665314043762954431722967712362 1 X X X X X X X X X X X X X X))
Selected main row:
(10252522186665314043762954431722967712362 1 X X X X X X X X X X X X X X)
Least number of common 1's is 0, which occurs in 1 side row(s):
((19 X 1 X X X X 1 X X X X X X X X))
Side row chosen:
(19 X 1 X X X X 1 X X X X X X X X)
Factors in exponent:
(1 1 5 7 11 13 1 29 887 1021 4729 5801 105359 472301 904219)
= 162251139143196199807888855520077235
Taking that side row to that power yields:
(6902237146718610265632378420713802956901 X 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
Multiplying main row by that, converted main row is now:
(19057625795975708314548816456832411347448 X X X X X X X X X X X X X X X)
Mininum number of 1's in any row is 0, which occurs in 1 row(s):
((19057625795975708314548816456832411347448 X X X X X X X X X X X X X X X))
** Primitive element: b=19057625795975708314548816456832411347448
which required 2 pivot(s)
.

Quantcast