Consider the Proth space
We will be using generating element 1+3^t
The [sub]groups generated by 1+3^t have low order [ a lot lower than n-1 ]
Tabulating the elements of groups generated by 1+3^t next
Using the prefix EPu to avoid clashing with existing letter conventions for groups.
Prefer G or S? Replace them in your local copy.
When t=2 we have P=1+10×27 and the set of elements modulo P is a multiplicative group.
Our generator 1+3^t is 10 and the subset it generates has 5 elements.
The elements in EPu5 are { 10, 100, 187, 244, 1 }
If EPu5 is really a group then we need inverses so let us document those next.
- Inverse of 10 is 244 mod P
- Inverse of 100 is 187 mod P
For 28 from t= 3 the elements in EPu42 are as shown next.
{ 28, 784, 1531, 2026, 3, 84, 83, 55, 1540, 9,
252, 249, 165, 82, 27, 756, 747, 495, 246, 81,
-1, 2241, 1485, 738, 243, 2266, 2185, 2186, 2214, 729,
2260, 2017, 2020, 2104, 2187, 2242, 1513, 1522, 1774, 2023,
2188, 1 }
The seventh to last element is always -27
The thirteenth to last element is always 729 alternatively written as 3^6
Every twelfth element after 3^6 from the end of the subgroup is a power of 3.
In order we would write them as follows
Writing them longhand we might say
- thirteenth from last is 3^6
- twentyfifth from last is 3^12
- …
- fortyninth from last is 3^24
- …
In calculation terms we can jump to any portion of our group and be at most 11 elements away from the element we require.
This can be a tremendous labour saver as instead of repeated powering to obtain an element of the subgroup, we can jump near our required element and then conduct a much smaller number of repeated powering to gain our result.
For 82 from t=4 the 27 elements in EPu27 are shown next.
{ 82, 6274, 13339, 17740, 9, 738, 735, 489, 244,
81, 6642, 6615, 4401, 2196, 729, 19924, 19681, 19682,
19764, 6561, 19900, 17713, 17722, 18460, 19195, 19684, 1 }
Conjecture: The number of elements in the group generated by 1+3^t working modulo P where P is 1+(1+3^t)*(3^(t+1)) must be a multiple of 1+2×t
For 244 from t=5 the 22 elements in EPu22 are not tabulated here
For 730 from t=6 the 39 elements in EPu39 are not tabulated here
For 2188 from t=7 the 90 elements in EPu90 are not tabulated here
For 6562 from t=8 the 17 elements in EPu17 are not tabulated here
For 19682 from t=9 the 114 elements in EPu114 are not tabulated here
For 59048 from t=10 the 63 elements in EPu63 are not tabulated here
For 177146 from t=11 the 46 elements in EPu46 are not tabulated here
For 531440 from t=12 the 75 elements in EPu75 are not tabulated here
For 1594322 from t=13 the elements in EPu162 are not tabulated here
For 4782968 from t=14 the elements in EPu29 are not tabulated here
For 14348906 from t=15 the elements in EPu186 are not tabulated here
For 43046720 from t=16 the elements in EPu99 are not tabulated here
For 129140162 from t=17 the elements in EPu70 are not tabulated here
For 387420488 from t=18 the elements in EPu111 are not tabulated here
For 1162261466 from t=19 the elements in EPu234 are not tabulated here
For 3486784400 from t=20 the elements in EPu41 are not tabulated here