On 28/09/2024 04:48, Mike Terry wrote:

On 28/09/2024 01:53, Peter Fairbrother wrote:

Note: most posters here don't go for top-posting, preferring responses intermixed with the original quoted text.  Just saying, because some
people will get cross with top posters!

I shall beat myself up immediately.

[...]

Is the set e^2^n mod p (where e is a generator and element of the
multiplicative group mod p, p is prime and n=0 to p) equal to the set
of quadratic residues of the group?

No - you could just try out a couple of low p examples to see it doesn't work.  E.g. p=7.

generators:     3 and 5
qres:           1,2,4

e:              3       5
              ---     ---
e^(2^0)         3       5
e^(2^1)         2       4
e^(2^2)         4       2
e^(2^3)         2       4
e^(2^4)         4       2
...

both are missing qr: 1

Ok, thanks for the help - I should have asked:

Is the set S = g^(2^n) mod p (where g is any generator / element of the multiplicative group mod p, p is prime and n=1 to p) plus the element 1
equal to the set QR of quadratic residues of the aforementioned group?

(Note we can calculate g^(2^n) = g^(2*2^(n-1)) = g^(2^(n-1))^2
iteratively by squaring, taking mod p after each iteration.

Yes, so we would never get a non-QR in S. But do we get all the QRs?

A proof?

Peter Fairbrother

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 29/09/2024 23:02, Peter Fairbrother wrote:

On 28/09/2024 04:48, Mike Terry wrote:

On 28/09/2024 01:53, Peter Fairbrother wrote:

Note: most posters here don't go for top-posting, preferring responses intermixed with the
original quoted text.� Just saying, because some people will get cross with top posters!

I shall beat myself up immediately.

[...]

Is the set e^2^n mod p (where e is a generator and element of the multiplicative group mod p, p
is prime and n=0 to p) equal to the set of quadratic residues of the group?

No - you could just try out a couple of low p examples to see it doesn't work.� E.g. p=7.

generators:���� 3 and 5
qres:���������� 1,2,4

e:������������� 3������ 5
�������������� ---���� ---
e^(2^0)�������� 3������ 5
e^(2^1)�������� 2������ 4
e^(2^2)�������� 4������ 2
e^(2^3)�������� 2������ 4
e^(2^4)�������� 4������ 2
...

both are missing qr: 1

Ok, thanks for the help - I should have asked:

Is the set S = g^(2^n) mod p (where g is any generator / element of the multiplicative group mod p,
p is prime and n=1 to p) plus the element 1 equal to the set QR of quadratic residues of the
aforementioned group?

(Note we can calculate g^(2^n) = g^(2*2^(n-1)) = g^(2^(n-1))^2 iteratively by squaring, taking mod
p after each iteration.

Yes, so we would never get a non-QR in S.

correct (given you're not considering n=0)

But do we get all the QRs?

I'm not sure what your question is. It sounds like you're asking whether for all [odd?] p and all
choice of generators g, the set S(p,g) U {1} = QR(p) ? I.e. do the conditions you describe imply
the conclusion that S(p) U {1} = {quadratic residues mod p}?

If so, what small p have you tried so far, and what was the result?

A proof?

Well if the conjecture fails, a counter-example suffices. But like I said, I'm not sure what you're
asking. It should be apparent from tests that some (p,g) values work and some do not.


Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Is the set e^2^n mod p (where e is a generator and element of the multiplicative group mod p, p is prime and n=0 to p) equal to the set of quadratic residues of the group?

Thanks

Peter Fairbrother

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

That cam out wrong, should be e^(2^n) mod p maybe?

e to the power (2 ^n) mod p

I don't know how to do multi-level superscripts in newsgroups, sorry.


Peter F


On 28/09/2024 01:31, Peter Fairbrother wrote:

Is the set e^2^n mod p (where e is a generator and element of the multiplicative group mod p, p is prime and n=0 to p) equal to the set of quadratic residues of the group?

Thanks

Peter Fairbrother

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 28/09/2024 01:53, Peter Fairbrother wrote:

That cam out wrong, should be e^(2^n) mod p maybe?

e to the power (2 ^n) mod p

I don't know how to do multi-level superscripts in newsgroups, sorry.

You could say e^(2^c). Given standard precedence rules that is the same as without the brackets,
i.e. e^2^c. [That's what you wrote I believe.]

But... my newsreader unhelpfully displays the latter using superscripts, which makes it look like
(e^2)^c, which is incorrect. Well, that's my problem I guess, not the poster's.

Note: most posters here don't go for top-posting, preferring responses intermixed with the original
quoted text. Just saying, because some people will get cross with top posters!

Peter F

On 28/09/2024 01:31, Peter Fairbrother wrote:

Is the set e^2^n mod p (where e is a generator and element of the multiplicative group mod p, p is
prime and n=0 to p) equal to the set of quadratic residues of the group?

No - you could just try out a couple of low p examples to see it doesn't work. E.g. p=7.

generators: 3 and 5
qres: 1,2,4

e: 3 5
--- ---
e^(2^0) 3 5
e^(2^1) 2 4
e^(2^2) 4 2
e^(2^3) 2 4
e^(2^4) 4 2
...

both are missing qr: 1

(Note we can calculate e^(2^n) = e^(2*2^(n-1)) = e^(2^(n-1))^2 iteratively by squaring, taking mod p
after each iteration. In the above table 3^2 = 2 [mod 7], 2^2 = 4 [mod 7], 4^2 = 2 [mod 7], then
pattern repeats...)

Obviously looking at e^(2n) gives quadratic residues, e.g. 3^0 = 1, 3^2 = 2, 3^4 = 4, which is
iteratively multiplying by e^2 = 2 [mod 7], but iteratively /squaring/ doesn't work.

Using a spreadsheet for testing is an easy way to investigate this sort of thing...


Regards,
Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Mike Terry <[email protected]> writes:

Well if the conjecture fails, a counter-example suffices. But like I
said, I'm not sure what you're asking. It should be apparent from
tests that some (p,g) values work and some do not.

Mod(3,17) is a generator, but its 2^n-th powers hit Mod(1,17) really
quickly.

Phil
--
We are no longer hunters and nomads. No longer awed and frightened, as we have gained some understanding of the world in which we live. As such, we can cast aside childish remnants from the dawn of our civilization.
-- NotSanguine on SoylentNews, after Eugen Weber in /The Western Tradition/

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 09/10/2024 17:21, Phil Carmody wrote:

Mike Terry <[email protected]> writes:

Well if the conjecture fails, a counter-example suffices. But like I
said, I'm not sure what you're asking. It should be apparent from
tests that some (p,g) values work and some do not.

Mod(3,17) is a generator, but its 2^n-th powers hit Mod(1,17) really
quickly.

Phil

Also p=13. Well, the powers don't hit 1, but quickly cycle with a period of 2. Cycling "too soon"
is the general way different primes fail, rather than specifically hitting 1.


Here's a different (simpler if correct) way of looking at things:

[note I'm only considering odd primes p...]

If g is a generator, the quadratic residues [mod p] will be g^0=1, g^2, g^4, ...g^(p-1). So the
question is whether g^2, g^4, g^8, g^16, ... g^(2^(p-1)/2) enumerates the same set.

This will be the same regardless of the generator chosen, as it is more about the powers of 2 [mod
p-1], rather than a QR question. Note that by Fermat's Little Theorem, 2^(p-1) = 1 [mod p] which is
why I reduce the exponents mod (p-1) rather than mod p which might be expected.

So it seems we want to know when 2 multiplicatively generates the even numbers [mod p-1]. Hmm, if
we divide everything by 2, maybe that becomes simply "2 generates the whole of Z mod (p-1)/2" ??

I'm not 100% sure on all this, but makes me think that perhaps for someone working in this area
(e.g. number theory) it would be easy for them to characterise which p work and give an explanation
why... I expect this would be well known. For me it is all too long ago - I was a student more
than 40 years ago, and even then I didn't do much number theory (which I regret slightly).

Just by inspection (mucking about in an Excel spreadsheet) it seems most p won't work due to 2^n
[mod p-1] quickly hitting a cycle, but a few p DO work, so there's an interesting question as to why.

Working p: (2), 3, 5, 7, 11, 23, 59, ...

(Then again I might have mucked up the spreadsheet or just misrecorded something, so don't take that
as gospel!)

Hmm, one more thing it reminds me of is expansions for fractions like 1/n. For certain n these
achieve a maximum length before repeating, whereas others do not. Like 1/7 = 0.142857[repeat], and
6 is the maximum length before the division is forced to repeat because there are only 6 possible
remainders at each step. Don't know if this is really relevant, it just brings this to mind for me.

Regards,
Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Mike Terry <[email protected]> writes:

On 09/10/2024 17:21, Phil Carmody wrote:

Mike Terry <[email protected]> writes:

Well if the conjecture fails, a counter-example suffices. But like I
said, I'm not sure what you're asking. It should be apparent from
tests that some (p,g) values work and some do not.

Mod(3,17) is a generator, but its 2^n-th powers hit Mod(1,17) really
quickly.

Also p=13. Well, the powers don't hit 1, but quickly cycle with a
period of 2. Cycling "too soon" is the general way different primes
fail, rather than specifically hitting 1.

Yeah, I chose 17 because it is a Fermat prime (of the form 2^n+1),
and I knew 2^n modulo EulerPhi(17)=16 would go 1, 2, 4, 8, 0, ...

Just by inspection (mucking about in an Excel spreadsheet) it seems
most p won't work due to 2^n [mod p-1] quickly hitting a cycle, but a
few p DO work, so there's an interesting question as to why.

Working p: (2), 3, 5, 7, 11, 23, 59, ...

(Then again I might have mucked up the spreadsheet or just misrecorded something, so don't take that as gospel!)

OEIS is the place to look for such sequences. It's probably something
trivial.

Phil
--
We are no longer hunters and nomads. No longer awed and frightened, as we have gained some understanding of the world in which we live. As such, we can cast aside childish remnants from the dawn of our civilization.
-- NotSanguine on SoylentNews, after Eugen Weber in /The Western Tradition/

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 10/10/2024 17:17, Phil Carmody wrote:

Mike Terry <[email protected]> writes:

On 09/10/2024 17:21, Phil Carmody wrote:

Mod(3,17) is a generator, but its 2^n-th powers hit Mod(1,17) really
quickly.

Also p=13. Well, the powers don't hit 1, but quickly cycle with a
period of 2. Cycling "too soon" is the general way different primes
fail, rather than specifically hitting 1.

Yeah, I chose 17 because it is a Fermat prime (of the form 2^n+1),
and I knew 2^n modulo EulerPhi(17)=16 would go 1, 2, 4, 8, 0, ..

A perhaps more important consideration is whether it is a "safe" prime
of the form p=2q+1, p and q both prime.



However, I was originally thinking about exponentiation by squaring. If
the cycling starts too soon then we might do exp-by-squaring faster, but
that's impossible if we use a generator - two different exponents would
give the same result.

To clarify, suppose we used p=17 and g=3 and the sequence ran 464646...
(it doesn't). To find g^7 we could calculate 4x6x4 = 4^2x6 = 6x6 = 4
just by knowing 4^2=6 and 6^2=4. But g^1 would also equal 4, which means
g is not a generator, a contradiction.



So, what are we left with? That the intro to the sequence, before it
starts repeating, must be at least as long as the number of bits in the
prime.


Peter Fairbrother

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)