Discussion:
group theory question
(too old to reply)
Peter Fairbrother
2024-09-28 00:31:22 UTC
Permalink
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
Peter Fairbrother
2024-09-28 00:53:44 UTC
Permalink
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
Post by Peter Fairbrother
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
Ross Finlayson
2024-09-28 01:24:26 UTC
Permalink
Post by Peter Fairbrother
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
Post by Peter Fairbrother
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
How about "where it is and where it isn't".

Conjectures, in the infinitary, are, abstract.
Here you can find a bit of square-free,
for example to make a conjecture,
then for example running out conjectures,
yet it's so that: in the infinitary,
like "when there are infinitely many residues"
and "there are infinitely many powers of e to
the 2n", how "e is usually log-normal", with
regards to "whatever's log normal to e,
when the exponent is also an exponent here 2^n",
that the inverse of exponent or log, is also
for making the inverse of 2^n, out of exponent,
in 2's-log and e's-log, those being inverses of
a sort, that it's b to the a to the n, those
"inverses" having "what it log" and "what is out
square log".


Then, conjectures in the infinitary are also
abstract, this is basically "whether or not
there is a point at infinity" and "whether or
not the point at infinity is a prime" and
"whether or not the point at infinity is
a double prime", and for example "... or a composite",
and "... of so many or all factors", a double trime,
a triple prime, a quadruple prime, each an abstract
model of numbers, making its own independent
infinitary conjectures.


Then also things like the quadratic sieve or
here the "Factorial/Exponential Identity",
is out in large spaces of numbers, about
emergence of convergence criteria, with
the fact that number theory is independent
a lot of things for "point at infinity" for
whatever the "point at infinity" is, in laws
of large numbers.

The quadratic starts adding up from the parabolic
and the quadratic sieve, that's in primes of the
squares, the quadratic sieve, then the parabola
also _focusing_ what falls into it, for example
is in the effects of focusing what goes out
"exponentially" in phase state transition, with
regards to phase being potentials in power,
"on and off" for example when "if it changed
must have gone exponential", then with regards
to being linear or exponential in a, b, c,
is just pointing out that for the expression,
are "laws of large numbers" and "criteria of convergence",
that the laws are theoretically "underdefined", "it is the law",
while criteria or unknowns yet emergent, "it is its law",
that "expressions in the infinitary always assume a
law of large numbers", then that they don't in the linear,
or algebra results balanced or reduced quotients,
the product inverses, then the changes in those,
when it's "per time" and whether "in time",
that residues and moduli in integer moduli,
and "field arithmetic and a clock arithmetic
a modular arithmetic", that in _groups_,
those two groups are always singular to each
other with more than one law of large numbers,
while for example otherwise it's classical,
groups relating or not.

So, "I don't know", yet "where it _is_ and where it _isn't_",
that the quadratic sieve "draws" primes, then as
with regards to "what x^e signless or magnitude, connected
like the parabola x^2", marks on integer and lattice points
like the quadratic sieve marks the composite numbers,
then for example whether infinity is prime, usually,
or composite, and draws out, prime at infinity.



This applies to many conjectures in number theory
because most all involve infinitary expressions.


The moduli, is maybe not dense to quadratic residues,
about the square-free, a ^ (b ^ n) mod p, moduli p,
also about where "a ^ (b^n)" and "a^b^n" fall out,
where I often notices that "a^b^n" falls out terms
to "a^(b^n)", when for example sign a =/= sign b.


Anyways in a catalog of sort of conjectures of
infinitary expressions, and the various models
where they are and aren't so according to whether
there is or isn't a point at infinity, for example,
here has that I can't make so much use of the
"2's-log and e's-log, when it's 2^e and e^2,
exponentiated", then has that the moduli, usually
has that in large numbers, those would be uniform
in the moduli, i.e. "in the class of residues zero mod p",
of e^(2^n) mod p, has whether larger moduli are or
aren't more likely to make quadratic residues,
whether or not the parabolic, fills out the quadratic,
for example according to whether or not there's a
point at infinity (a single point at infinity)
that is connected or not by the quadratic sieve
and always falls _in_, lower numbers what get
drawn, whether or not it fills out and there's
also a point at infinity, so that besides it's
density going to zero in the infinite, that it
also has a "non-zero density floor", which stands
in for its condition in convergence criterion condition,
whether or not there's a point at infinity.

Then, it either sort of is or isn't these those,
while it's sort of so, yet there's also whether
primes, i.e. "residues, or primes, or integral
moduli", here the most comforting step usually
being the "square-free", or that for number theorists
much applied sits in the square-free, or that's my
impression, then also for "square-free or also
some kind of log-free", then also for the existence
besides in terms, of the constants, when those would
"suffice in the same way", that the density going
down the line would tend to add up or even out.
Mike Terry
2024-09-28 03:48:28 UTC
Permalink
Post by Peter Fairbrother
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!
Post by Peter Fairbrother
Peter F
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.
Peter Fairbrother
2024-09-29 22:02:53 UTC
Permalink
Post by Mike Terry
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.

[...]
Post by Mike Terry
Post by Peter Fairbrother
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?
Post by Mike Terry
(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
Mike Terry
2024-09-30 01:29:00 UTC
Permalink
Post by Peter Fairbrother
Post by Mike Terry
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.
[...]
Post by Mike Terry
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
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?
Post by Mike Terry
(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)
Post by Peter Fairbrother
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?
Post by Peter Fairbrother
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.
Phil Carmody
2024-10-09 16:21:34 UTC
Permalink
Post by Mike Terry
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/
Mike Terry
2024-10-10 04:06:07 UTC
Permalink
Post by Phil Carmody
Post by Mike Terry
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.
Phil Carmody
2024-10-10 16:17:37 UTC
Permalink
Post by Mike Terry
Post by Phil Carmody
Post by Mike Terry
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, ...
Post by Mike Terry
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/
Peter Fairbrother
2024-11-01 00:03:41 UTC
Permalink
Post by Phil Carmody
Post by Mike Terry
Post by Phil Carmody
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

Loading...