Consider the Proth space
We will be using generating element 1 + 2^t
The [sub]groups generated by 1+2^t have low order [ a lot lower than n-1 ]
A related Conjecture is given next.
Conjecture: Order of 1+2^t mod P when P is prime and P of the form 1+(1+2^t)*(2^(t+1)) divides Lcm(2+4×t−(t+1),2+4×t)
Tabulating the elements of groups generated by 1+2^t next.
Using the TPy to avoid clashing with existing letter conventions for groups. Prefer G or S? Replace them in your local copy.
For 5 from t=2 the 20 elements in TPy20 are as shown next
{ 5,25,2,10,9,4,20,18,8,40,36,16,39,31,32,37,21,23,33,1}
which when put in numeric order are
1,2,4,5,8,9,10,16,18,20,21,23,25,31,32,33,36,37,39,40
Elements that do not appear are as shown next
3,6,7,11,12,13,14,15,17,19,22,24,26,27,28,29,30,34,35,38
When t=3 we have P=1+9×16 and the set of elements modulo P is a multiplicative group.
Our generator 1+2^t is 9 and the subset it generates has 14 elements.
The elements in TPy14 are
{ 9,81,4,36,34,16,144,136,64,141,109,111,129,1 }
If TPy14 is really a group then we need inverses so let us document those next.
- Inverse of 9 is 129 mod P
- Inverse of 81 is 111 mod P
- Inverse of 4 is 109 mod P
- Inverse of 36 is 141 mod P
- Inverse of 34 is 64 mod P
- Inverse of 16 is 136 mod P
For 17 from t=4 the 36 elements in TPy36 are as shown next
{ 17,289,8,136,132,64,543,511,512,529,
273,281,417,4,68,66,32,-1,528,256,
537,409,413,481,2,34,33,16,272,264,
128,541,477,479,513,1 }
For 33 from t=5 the 11 elements in TPy11 are as shown next
{ 33,1089,16,528,520,256,2109,1981,1983,2049,1 }
For 65 from t=6 the 52 elements in TPy52 are as shown next
{ 65,4225,32,2080,2064,1024,8313,7801,7805,8065,
2,130,129,64,4160,4128,2048,8305,7281,7289,
7809,4,260,258,128,8320,8256,4096,8289,6241,
6257,7297,8,520,516,256,8319,8191,8192,8257,
4161,4193,6273,16,1040,1032,512,8317,8061,8063,
8193,1 }
The fifth to last element is always -4
Every eighth element after 16 from the end of the subgroup is a power of 2.
In order we would write them as follows
Writing them longhand we might say
eight from last is 16
sixteenth from last is 2^8
twentyfourth from last is 2^12
…
eightieth from last is 2^40
In calculation terms we can jump to any portion of our group and be at most 7 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 129 from t=7 the 30 elements in TPy30 are as shown next.
{ 129, 16641, 64, 8256, 8224, 4096, 33009, 30961, 30969, 32001,
4, 516, 514, 256, -1, 32896, 16384, 32961, 24769, 24801,
28929, 16, 2064, 2056, 1024, 33021, 32509, 32511, 32769, 1 }
The fourth element can be obtained as
8256==Mod(-4,33025)^-1 alternatively
The eighth element can be obtained as
30961==Mod(16,33025)^-1 alternatively
For 257 from t=8 the 68 elements in TPy68 are as shown next.
{ 257, 66049, 128, 32896, 32832, 16384, 131553, 123361,
123377, 127489, 8, 2056, 2052, 1024, 131583, 131071,
131072, 131329, 65793, 65921, 98817, 64, 16448, 16416,
8192, 131569, 127473, 127481, 129537, 4, 1028, 1026,
512, -1, 131328, 65536, 131457, 98689, 98753, 115201,
32, 8224, 8208, 4096, 131577, 129529, 129533, 130561, 2, 514
513, 256, 65792, 65664, 32768, 131521, 115137, 115169, 123393, 16,
4112, 4104, 2048, 131581, 130557, 130559, 131073, 1 }
Conjecture: The number of elements in the group generated by 1+2^t working modulo P where P is 1+(1+2^t)*(2^(t+1)) must be a multiple of 1+2×t
For 513 from t=9 the 19 elements in TPy19 are as shown next
{ 513, 263169, 256, 131328, 131200, 65536, 525249, 492481,
492513, 408929, 16, 8208, 8200, 4096, 525309, 523261,
523263, 524289, 1 }
For 1025 from t=10 the 84 elements in TPy84 are not tabulated here
For 2049 from t=11 the 46 elements in TPy46 are not tabulated here
For 4097 from t=12 the elements in TPy100 are not tabulated here
For 8193 from t=13 the 27 elements in TPy27 are not tabulated here
For 16385 from t=14 the elements in TPy116 are not tabulated here
For 32769 from t=15 the elements in TPy62 are not tabulated here
For 65537 from t=16 the elements in TPy132 are not tabulated here
For 131073 from t=17 the elements in TPy35 are not tabulated here
For 262145 from t=18 the elements in TPy148 are not tabulated here
For 524289 from t=19 the elements in TPy78 are not tabulated here
For 1048577 from t=20 elements in TPy164 are not tabulated here
Using sturdy element notation we might say the results tabulated in this post are
