Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.math > #631705 > unrolled thread

group theory question

Back to article view | Back to sci.math

Contents

  group theory question Peter Fairbrother <peter@tsto.co.uk> - 2024-09-28 01:31 +0100
    Re: group theory question Peter Fairbrother <peter@tsto.co.uk> - 2024-09-28 01:53 +0100
      Re: group theory question Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-09-27 18:24 -0700
      Re: group theory question Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2024-09-28 04:48 +0100
        Re: group theory question Peter Fairbrother <peter@tsto.co.uk> - 2024-09-29 23:02 +0100
          Re: group theory question Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2024-09-30 02:29 +0100
            Re: group theory question Phil Carmody <pc+usenet@asdf.org> - 2024-10-09 19:21 +0300
              Re: group theory question Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2024-10-10 05:06 +0100
                Re: group theory question Phil Carmody <pc+usenet@asdf.org> - 2024-10-10 19:17 +0300
                  Re: group theory question Peter Fairbrother <peter@tsto.co.uk> - 2024-11-01 00:03 +0000

#631705 — group theory question

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

[toc] | [next] | [standalone]

#631706

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
> 
> 

[toc] | [prev] | [next] | [standalone]

#631707

On 09/27/2024 05:53 PM, 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.
>
>
> 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
>>
>>
>

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.

[toc] | [prev] | [next] | [standalone]

#631708

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.

[toc] | [prev] | [next] | [standalone]

#631748

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

[toc] | [prev] | [next] | [standalone]

#631755

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.

[toc] | [prev] | [next] | [standalone]

#632245

Mike Terry <news.dead.person.stones@darjeeling.plus.com> 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/

[toc] | [prev] | [next] | [standalone]

#632264

On 09/10/2024 17:21, Phil Carmody wrote:
> Mike Terry <news.dead.person.stones@darjeeling.plus.com> 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.

[toc] | [prev] | [next] | [standalone]

#632270

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> On 09/10/2024 17:21, Phil Carmody wrote:
>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> 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/

[toc] | [prev] | [next] | [standalone]

#633130

On 10/10/2024 17:17, Phil Carmody wrote:
> Mike Terry <news.dead.person.stones@darjeeling.plus.com> 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

[toc] | [prev] | [standalone]

Back to top | Article view | sci.math

csiph-web