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 ENt to avoid clashing with existing letter conventions for groups. Prefer G or S? Replace them in your local copy.
For 8 from t=2 elements ENt5 are { 8, 64, 78, 190, 1 }
For 26 from t= 3 the elements in ENt42 are as shown next.
{ 26, 676, 720, 1864, 3, 78, 2028, 53, 1378, 9
234, 1870, 159, 2027, 27, 702, 1396, 477, 1867, 81
2106, 2081, 1431, 1387, 243, 2104, 2029, 79, 2054, 729
2098, 1873, 237, 1948, 80, 2080, 1405, 711, 1630, 240
2026, 1 }
When t=4 we have P=1+80×243 and the set of elements modulo P is a multiplicative group.
Our generator −1+3^t is 80 and the subset it generates has 27 elements.
The elements in ENt27 are as shown next
{ 80, 6400, 6534, 17254, 9, 720, 18718, 483, 19199, 81,
6480, 12934, 4347, 17263, 729, 19438, 19201, 241, 19280, 6561,
19414, 17281, 2169, 17992, 726, 19198, 1 }
If ENt27 is really a group then we need inverses so let us document those next.
- Inverse of 80 is 19198 mod P
- Inverse of 6400 is 726 mod P
- Inverse of 6534 is 17992 mod P
- Inverse of 17254 is 2169 mod P
- Inverse of 9 is 17281 mod P
- Inverse of 720 is 19414 mod P
- Inverse of 18718 is 6561 mod P
- Inverse of 483 is 19280 mod P
- Inverse of 19199 is 241 mod P
- Inverse of 81 is 19201 mod P
- Inverse of 6480 is 19438 mod P
- Inverse of 12934 is 729 mod P
- Inverse of 4347 is 17263 mod P
For 242 from t=5 the 22 elements in ENt22 are as shown next
{ 242, 58564, 58968, 156736, 27, 6534, 169876, 4365,
174235, 729, 176418, 176177, 117855, 117451, 19683, 176392,
169885, 6543, 172054, 2184, 175690, 1 }
The seventh to last element is always -27
The thirteenth to last element is always 729 alternatively written as 3^6
For 728 from t=6 the 39 elements in ENt39 are as shown next
{ 728, 529984, 531198, 1414990, 81, 58968,
1533142, 39339, 1572463, 6561, 1592134, 1589953,
2185, 1590680, 531441, 1591894, 1415233, 176985,
1474120, 59022, 1572454, 9, 6552, 1585582,
4371, 1589951, 729, 530712, 1061182, 354051, 1415071, 59049,
1592110, 1572481, 19665, 1579024, 6558, 1589950, 1 }
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 2186 from t=7 the 90 elements in ENt90 are as shown next.
{ 2186,4778596,4782240,12748024,243,531198,
13811068,354213,14165227,59049,14342338,14322673,
19677,14329228,6560,14340160,9561565,4781511,
11154430,1594080,13810906,81,177066,14165254,
118071,14283307,19683,14342344,14335789,6559,
14337974,4782969,14341618,12748753,1593837,13279708
531360,14165200,27,59022,14283316,39357,
14322667,6561,-1,14340161,9563751,9560107,
1594323,14342104,13811149,531279,13988134,177120,
14283298,9,19674,14322670,13119,14335787,
2187,4780782,9560836,3187917,12748267,531441,
14342266,14165281,177093,14224276,59040,14322664,
3,6558,14335788,4373,9559378,729,
1593594,12748510,1062639,13810987,177147,14342320,
14283325,59031,14302990,19680,14335786,1 }
The sixth element can be obtained as 531198==Mod(-27,14342347)^-1 alternatively
The twelfth element can be obtained as 14322673==Mod(729,14342347)^-1 alternatively
For 6560 from t=8 the 68 elements in ENt17 are as shown next.
{ 6560, 43033600, 43044534, 114771574, 729, 4782240,
124337998, 3188403, 127526239, 531441, 129120454, 128943361,
177129, 129002392, 59046, 129100798, 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 19682 from t=9 the 114 elements in ENt114 are not tabulated here
For 59048 from t=10 the 63 elements in ENt63 are not tabulated here
For 177146 from t=11 the 46 elements in ENt46 are not tabulated here
For 531440 from t=12 the 75 elements in ENt75 are not tabulated here
For 1594322 from t=13 the elements in ENt162 are not tabulated here
For 4782968 from t=14 the elements in ENt29 are not tabulated here
For 14348906 from t=15 the elements in ENt186 are not tabulated here
For 43046720 from t=16 the elements in ENt99 are not tabulated here
For 129140162 from t=17 the elements in ENt70 are not tabulated here
For 387420488 from t=18 the elements in ENt111 are not tabulated here
For 1162261466 from t=19 the elements in ENt234 are not tabulated here
For 3486784400 from t=20 the elements in ENt41 are not tabulated here