All My Notes On Solving Modular Square Root In BQP With an Oracle For GENERATORS

updated, 04-21-2026, 1:10 p.m.

All steps and most facts for MSR proof.

1 - Use the railtracks definition from the other file, DL.txt.  Call it "tracks" not "railtracks."

2 - Recall that we have a "generator oracle," that takes as input an integer M and strings of bits and blanks and returns true if the blanks could be filled in with bits so that the final bit string represents a generator of the integer M.

3 - Given the integer M:  Use Shor's algorithm to factor it into prime factors.  Then, using the Chinese Remainder Theorem, take a in the expression x^2 = a (mod M), and write it as:  a (mod p_1^k_1), a (mod p_2^k_2), ... , a (mod p_j^k_3) ...where j is the number of distinct prime factors that M has.

4 - Now, find generators for each group (mod p_i^k) for each integer i from 1 to j.  Use the oracle, which works for any modulus integer p^k where p is prime and k is a natural number, including 1.

5 - Importantly, if we fix an arbitrary one of our moduli p_i^k_i, if the modulus value M is such that we are considering a = M (mod p_i^k_i), then we can easily test M to see if it *has* a generator mod p^I*k_i...we just use the oracle to figure it out, to find the generator bit by bit, if it exists.  If there is no generator for M (mod p_i^k_i) for any modulus p_i^k_i for one fixed I value, then there is no generator for the overall number a, and no generator for M, and thus, there is no square root (prove that!  We might have to use the notes in the note, "Dl notes" to write out a proof).

// update to #6:  See the note below at 2:25 p.m.  We need to use the generator H = gcd(M,a)*G.

// Also:  Prove that multiplying a generator for Z_M* by a track value gcd(M,a) yields a generator for that track, modulo M.

6 - Now, since we were given:  x^2 = a (mod M) ...we must select the generator that works that will generate a, in Z_M*.  To do that, we use the generators found in step 3, using the oracle.  The generator is found by selecting the generator for each modular group (mod p_i^k) and computing the resulting expression using the Chinese remainder theorem.  The claim is, the generator for each component modulus is congruent modulo that modulus to the modulus of the generator for the overall formula.  (Note, we are using an oracle that finds *only* generators modulo a group that has a prime power as the modulus.  We are using that oracle to find moduli for more complex values, too.  The claim is that it is easier in real life to find generators for prime numbers and prime powers, so we restrict our oracle to doing that.)  So now we have the generator for M, if it exists.  The generator will be called G.

7 - Now we take:  DL_G(x^2) = DL_G(a) (mod M) .

8 - Next, consider 2 * DL_G(x) = DL_G(a) (mod M) .

9 - Now, compute R = DL_G(a) (mod M).  Take R (mod M) and reduce it to an integer in [0, M-1].  Note, if there are many values for R, characterize them with a polynomial.

10 - If DL_G(a) is not even, then the square root does not exist.

11 - Now, take DL_G(x) = R/2 (mod M).  Let S = R / 2.

12 - Now consider:  G^(DL_G(x)) = G^(S) (mod M)

13 - Now:  x = G^S (mod M).  Compute G^S, and take it (mod M).  We have our solution!

Things to prove:

 - If a generator does not exist for one of the moduli p^k for the decomposition of M, then there is no generator for M.

 - If a generator does exist for every modulus p^k for the composition of M, then there exists at least one generator for M such that the generator (mod M) is equal to all of the values Q (mod p^k) for each prime power where Q is a generator for Z_(p^k)*.

 - The tracks facts (see the other file).

 - If none of the values of R in step 9 are ever even, the square root does not exist.  If there exists an even number that is congruent to R, then there does exist a square root.

That's not too bad!

There might be some more facts that I have missed.

:).

1:51 p.m.

Try to prove or disprove:  If an integer g is a generator for a group Z_p* where p is prime, then for any integer k >= 1, g is also a generator for Z_(p^k)*.

2:00 p.m.

(Just write a simple computer program investigating this for M = 23 and M = 23^5.

It might be a proof by induction, if a proof exists.  If it's true, it's probably the case that there's a proof by induction.

Remember, we don't need all the generators...just 1.  So find a generator mod p, then use it as the generator for mod p^k.  Don't be lazy--investigate this!

Cite Google AI if and only if you use the thing it said.  I probably will...I will probably mention Artin's constant.  It's not a big deal.  Use your money to get the cert from the university for the academic paper writing course...then you will not be ignored as much.

2:25 p.m.

Note:  We need to multiply the generator by something if the value of a is not coprime to the modulus M.  In particular, we need to just take the original generator G and multiply it by gcd(M,a) to form h = G * gcd(M,a).  This is the generator we will use in the DL problem.  The claim, which needs to be proved, is that this will generate all the values on the given "track."

04-22-2026

11:38 a.m.

When we use the Chinese remainder theorem, we get a series of moduli that are of the form p_i^k_i, where k is an integer >=1 and p is a prime.

Each congruence modulo each modulus p_i^k_i has three possibilities:

 - It shows that the value is on "track" for the value p_k.

 - It is a bad factor, meaning that we are currently on a "tail"--a non-loopy predecessor to the track--of the track that we will have temporarily before we eventually get on to the track value, i.e., enough multiplication by the overall value being examined with CRT will lead this modulus, and all other moduli with "bad factors," to eventually equal 0 modulo this modulus, meaning we *will be* on the track later.

 - It is a generated value--coprime to p^k--and we can use our generator oracle to find a generator for this modulus, which will be based on finding a generator for Z_p* and then using our proof (not yet found) that all generators for Z_p* are also generators for Z_(p^k)*.

The idea is, once we have all the tracks settled, and once we have the generators found, we can identify a new value, modulo all the moduli from the CRT, where the on-track values stay and the bad-factor values are set equal to 0 for that modulus, and the moduli for the other values will each be such that the value modulo that modulus is equal to the generator we found for Z_p* and therefore for Z_p*.  Crucially, *this value is a generator for the track that contains a modulo M*, where a is the value that we are taking the square root of, and M is the modulus.

That is, we have found a generator that will generate the value a as one of its values modulo M...and all other values on that "track".

2:14 p.m.

************************************************************************************************

BIG CLAIM:

For every integer A and every positive modulus M:

A is either on a track of M or on a tail of M, or, A is an element of Z_M*.  (The elements of Z_M* are all of the integers I in [0,M-1] such that I is coprime to M.)

************************************************************************************************

2:32 p.m.

ANOTHER BIG CLAIM:

For positive integer modulus M, given a in x^2 = a (mod M):

If a is on a track for mod M, then a square root exists; use the DL with a generator for the track of Z_m (which you find by finding generators for each M component in the CRT p^k, which you can find by finding any generator for Z_p*, and setting all of the values for this new generator equal to the generator for Z_(p^k)*), and apply it to both sides of the equation, etc., until you arrive at a solution.

If a is coprime to M, select any generator of Z_M* (using the Chinese Remainder theorem approach with different factors p^k of M), and use it as the DL generator and do the same thing above, take the DL of both sides, etc.

If a is on a tail for a track mod M, then we need to go into the CRT expression of a, and find every modulus relative to which a is a bad factor, or 0.  If there exists one modulus Y=p^k relative to which a = p^j where j < k and j > 0 and j is odd, that means that the square root of a does not exist.  Otherwise, we know that the square root must be equal to, for all moduli where the modulus Y = p^k and a = p^j where j < k and j > 0 and j is *even*, the square root of a is equal to p^(j/2) (mod p^k).  Thus, we can select p^(j/2) (mod p^k) as a new value for this process.  The next thing we will do is, run this idea again...let w = j/2 this time, and then ask, does there exist one modulus Y=p^w relative to which a = p^q where q < w and q > 0 and q is odd?  If so, stop the process, and select this set of numbers as the "maximally square-rooted" number, i.e., there is no number further back on any of the tails that could generate the value of a or any of its square roots or any of those numbers' square roots, etc.; we have reached the end of the line, which must exist because each exponent k is finite.  So what we do now is, we select something based on these modular congruences as our generator.  For all moduli where a = 0, preserve that and have G = 0 moduli all those moduli, too.  For all moduli where we had a bad factor and "backtracked square-root-wise," we set each modulus equal to the value of the moduli with "bad factors" where there was no more ability to universally (over all those moduli) continue taking square roots.  For all other moduli--which are moduli where a is coprime--we can select any number that is a generator for each modulus p^k, so, we select every such modular congruence to have a = g (mod p^k) where g is a generator for Z_p* and therefore also for Z_(p^k)* as well (if I can prove my proof that that works), for all of those integers p^k, where the value of each modular congruence had always been coprime to a, the value we're taking the square root of.

Now, if we use this number, found via the CRT, as our generator, it ought to work.

2:59 p.m.

Update:  Can we do it without DL??  Maybe we only need factorization.

Recall the big claim:

For every integer A and every positive modulus M:

A is either on a track of M or on a tail of M, or, A is an element of Z_M*.  (The elements of Z_M* are all of the integers I in [0,M-1] such that I is coprime to M.)

Maybe the idea is, we write out the number with the CRT with all the moduli being of the form p^k.  Then, we leave the = mod 0 parts alone.  We take the parts that are equal to "bad factors" and apply, to all of them, the repeated "square root" thing until we have no more that we can do.  The maximum number of square roots is ceil(log_2(k_max)), where k_max is the integer such that the largest of the p^k moduli can be written as p^k_max.

For all the other moduli, when the integer a value in [0, p^k-1] is congruent to something coprime to p (mod p^k), we just take the square root using "traditional techniques."  Maybe we can do it with Shanks' square root algorithm.  (Don't ask AI!)

Yes!  That works!

Check out:  https://en.wikipedia.org/wiki/Tonelli–Shanks_algorithm

3:09 p.m.

Oh:  The problem is, Shanks works modulo p...not modulo p^k.

The challenge problem is, find square roots modulo p^k.

3:12 p.m.

Oh:  Just use the DL algorithm for each individual square root problem mod p^k.  If the value is coprime to the modulus p^k, then you just need to find a generator for p^k...which we can find either using the oracle for generators directly, or, using the oracle for generators for prime moduli only.  Then we use the algebraic logic to find the square root modulo p^k.  It's that easy.

We don't need Shanks' algorithm.

3:17 p.m.

The only actually hard challenge is not even necessary for the overall proof:  Prove that all generators for Z_p* are also generators for Z_(p^k)*

3:29 p.m.

OK, so it's good that this works...but it's not really new.  The actually NP-complete version of the problem is:

x^2 = a (mod M), and, x is an integer in [0,C], where C is a positive integer < M

So the comment is, you can't do it unless you place an upper bound on the square root.

The challenge is, we need to find *exhaustively* *all* the square roots.

I think the comment is, we can do it.

Recall the three possibilities.

 - For bad factors involved:  step back the square root as much as you can.  There's a small limit on how many times you can do it.  Each time, there will only be *one* square root.

 - For no bad factors, no "tracks":  just use the DL approach.  You'll find every factor by finding every DL.  We're assuming here that the DL algorithm will output all of the discrete logarithms, succinctly represented in something like a modular formula.

 - For "tracks":  Preserve the tracks being at the same value...= 0 (mod p^k).

And the idea is, we only compute using the DL technique directly when we are dealing with "no bad factors, no tracks".  If there are tracks, we still use the DL technique on the other moduli with no tracks and no bad factors linked to them individually.

I think this is good!  Think about it some more.  Try to prove the "hard theorem."  I think this is the answer.

3:39 p.m.

For any overall mod problem:

 - For all the "tracks" moduli:  Leave the modulus at 0, if the value of the k value in p^k the modulus is odd.  Otherwise, treat the track as a possible "bad factor" modulus.  It's not really a bad factor though.  So you take the possible square roots of 0 here, for each mod with an even k value...and that yields basically, p^(k/2) and 0.  Next step, it will be, p^(k/4) and 0.  Etc.

 - For all the "bad factor values" moduli:  Take all of them together in connection with each other, and back track by taking the square root until you have reached a value for at least one of the moduli congruences where no more progress can be made.  Count how many times you have done this--call that number Q.

 - For all the "the value is coprime to p^k" moduli:  Use the DL approach to generate a formula for all of the square roots.

Ultimately:  See how many times you "backtracked" in step 2, including with the moduli that were "tracks" moduli with even powers.  Then, take the square roots that you found using the DL technique in step 3.  Take the square roots iteratively, back to however many times you backtracked in steps 1 and 2.  Now, take each of these values, and step them forward until you reach all of the square roots of the original value a--one step before.  This gives you all of the square roots.  The key is, we have to *step forward through the square roots we found with the DL technique*.

Or do we?

It looks like, no, actually, we only need to step back once.

So again:

3:45 p.m.

 - For all the tracks moduli:  If the power is odd, leave them.  If the power is even, step back *once*, and consider both of these two values:  0, p^(k/2).

 - For all the bad factors value moduli:  Take them all together, along with the values in the step above, and step back *once*.  If the values exist in every case, save those values as possible square roots for each modulus.

 - For the "value is coprime to the modulus" moduli:  Use the DL approach to find a formula for all the square roots of this value.

Then, just combine all the facts you know, and see if any of the values are less than C!

************************************************************************************************

// So really, there are four cases:

// Update:  4-24, 2:43 p.m.:  There are FIVE cases, for each congruence modulo p^k:

1 - modulus is on the track, based on the value, the p power is odd

2 - modulus is on the track, based on the value, the p power is even

3 - modulus has a "bad factor" as the value for the congruence, the p power is odd

4 - modulus has a "bad factor" as the value for the congruence, the p power is even

5 - modulus is coprime to the value

************************************************************************************************

************************************************************************************************

We lump #2 and #3 in together.

3:49 p.m.

Issue:  What if the bad factor is not exactly a value of the form p^j?  What if it's, say, 4*p^j (mod p^k)?  What do we do then?

I think the answer is:

Take the square root of 4 mod M

Take the square root of p^j mod M

Multiply those together.  The way to take 4 mod M is, it must be coprime to p^k, so we just use #4 to do that part.

Great!! :)

************************************************************************************************

3:59 p.m.

Claim:  Every DLP solver algorithm will return something like this:

DLP(g, a, M) = x (mod F), where F is a positive integer s.t. F|M

Prove that!

In particular, prove that there is only one value x modulo F that is "returned."

5:52 p.m.

************************************************************************************************************************************************************************************************************************************************************************************************

How to organize this argument for clarity:

 - Define tracks.

 - Define tails.

 - Conjecture:  Every track has at least one generator.

 - Focus on this BIG CLAIM:  For every integer A and every positive modulus M:  A is either on a track of M or on a tail of M, or, A is an element of Z_M*.  (The elements of Z_M* are all of the integers I in [0,M-1] such that I is coprime to M.)

 - A proposition that may not be that important:  Every element that is on a tail is not an element of any track.

 - Focus on these four cases, for each of the prime power moduli that are decomposed to in CRT:

// 04-24, 2:44 p.m.:  SEE ABOVE, THERE ARE ACTUALLY 5 CASES

// 1 - modulus is on the track, based on the value, the p power is odd

// 2 - modulus is on the track, based on the value, the p power is even

// 3 - modulus has a "bad factor" as the value for the congruence

// > Note, the bad factor might be congruent to q*p^k, where gcd(q,p) = 1.

// 4 - modulus is coprime to the value

 - Focus on these four responses to the four cases:  // close enough, adopt it to all 5 cases

1 - no square root exists...halt stepping back if this ever happens

2 - a square root exists, either it's =0 (mod p^k) or =p^(k/2) (mod p^k), step it back

3 - if j in q*p^j is odd, halt stepping back; if the j value is even, try to step back

if other values allow it, to p^(j/2) * sqrt(q); calculate sqrt(q) using the

method in step 4 here...note, here, q*p^j is the a-value, the modulus is p^k .

4 - use the DL system to calculate the square root, if it exists; you'll get a formula

for all of the solutions, "b (mod c)", where c is a factor of q*p^k

 - Each time, if any of the sqrts doesn't exist, or one of the "step backs" doesn't work, you halt stepping back.  Note, we are actually ONLY going to step back ONCE.  If the single step-back works, we have a sqrt that exists, and we're done.  If ONE of the step-back methods fails, the whole thing fails, and we have that no square root exists.

************************************************************************************************************************************************************************************************************************************************************************************************

Is this everything??  Not quite.  We have to handle the four cases.

6:01 p.m.

You have to write all this very clearly.  All of the proofs should be simple and obvious.  Write out every step!  Maybe write it like a logic proof.  Don't be afraid to involve modus ponens in this.  Prove all the steps.  Write about "fix an arbitrary a," whatever.  Prove a-->b statements and universally quantified statements.  That's probably a good start for how to go about this!  The definitions are easy--we can define tracks and tails, that's fine.

Given any modulus M, if there are Z factors of M, then there are Z tracks of M.  Every track is based on one distinct factor of M.  The track for 1 is the "coprime" track--we might call it that.  The track for M is the "zero" track.  Every other track is different.  Some tracks have a tail, which is when an element outside of the track can, via exponentiation, enter the track.  Sometimes, the element from the tail that enters the track does not actually lead to the generation of the entire track.  Nevertheless:  Conjecture:  every track has a generator.

6:29 p.m.

Basically, what I have is an algorithm, and a few facts that seem to be true.  The challenge is, how do you prove that your algorithm works?  I think the key is, we need to define the algorithm as a particular *function*.  We need to show that the function runs in BQP, with a particular oracle, by showing that other than Shor's algorithm and the generator oracle, the algorithm is fully just PTIME.  Then, we need to somehow show that the function is logically equivalent to the modular square root function.  How exactly do we do this?  In general, how do we demonstrate logical equivalence of two functions?

Maybe we could do a proof by contradiction.  Begin with the function in question, then, run it on something, consider the output, and assume for the sake of contradiction that the output, squared, is not equal to the input.  Find a contradiction and you're done.

6:32 p.m.

How many times do we query Shor's algorithm?  I think:  We use it to factor M, and, we use it to calculate the DL up to R times, where R is the number of prime powers that are factors of M.

How many times do we query the generator oracle?  Let's abandon the search for the proof that every generator of Z_p* yields a generator for Z_(p^k)*.  Is there always a generator for Z_(p^k)*?  I think that's the last existential challenge with this proof, is make sure that's true.

Maybe I will try to find a proof of the claim, though, if there's no other way to show that mod p^k always has a generator for the group formed form its coprime to p^k elements!

You could prove that the algorithm is polynomial time by treating it as a C-like or Python-like language, and showing that all of the "for loops" are finitely nested and linearly terminating.

You could include pseudocode, or even a Python implementation.

04-23

11:16 a.m.

Claim:  Even if Shor's algorithm only returns one integer, we can still test every factor of the modulus M for the DL inputted to Shor's algorithm, and find the smallest modulus that we need to say that the DL is equal to modulo that modulus...the interval such that adding the interval to the one DL yields more DLs, modulo M, given the inputted DL problem.

11:27 a.m.

************************************************************************************************

Use the Chinese remainder theorem and the fact that it preserves multiplication to prove that your algorithm works.  You just show, if you take the square root modulo each modulus p^k, you will obtain the square root modulo M = the product of all the p^k terms.  In particular, if you multiply a number by itself modulo each modulus, that yields the same value as that product modulo each p^k factor modulus.

************************************************************************************************

We just need to show each algorithm for taking the square root for the different moduli works.  There are four possible types of case.

************************************************************************************************

For #1 and #2, we have to prove that no value other than p^(k/2) works when k is even and when k is odd, no value works.

For #3, we need that technique also...but we also need the second technique, the DL approach, if q != 1.  We need the second technique for #4, too.

So there are two techniques:  the step-back technique, and the DL technique.

************************************************************************************************

11:43 a.m.

************************************************************************************************

Possible list of definitions:

 - The step-back square root method.

 - The discrete-logarithm square root method.

 - Track. // closed under exponentiation!

 - Coprime environment. // also closed under exponentiation!

 - Tail.

 - Bad factor.

 - Generator candidate. // for both a track and for coprime environment

************************************************************************************************

************************************************************************************************

4-23, 1:08 p.m.

Possible list of Theorems:

 - CRT preserves square root existence and value.

 - Given a fixed modulus M, every integer A is either an element of exactly one of the following three items:  exactly one specific track, the tail of exactly one specific track, or the coprime environment.

 - The step-back square root method works for appropriate pairs of value and modulus (track or tail) for determining the existence of a square root and finding its value.

 - The discrete-logarithm square root method works for appropriate pairs of value and modulus (coprime environment) for determining the existence of a square root and finding its value.

 - Modular square roots are multiplicative, i.e., a*b (mod M) is such that the square root of a*b (mod M) is equal to sqrt(a) (mod M) * sqrt(b) (mod M), and, a*b's square root exists if and only if a's and b's square roots both exist.

 - For all of the four cases defined above (within the three lines of stars), the square root's existence and value can be calculated, and this implies that any modular square root's existence and value can be calculated.

************************************************************************************************

Later, try to list all of the propositions that we will need to prove.

https://en.wikipedia.org/wiki/Generating_set_of_a_module

I'm not sure about the p^k generator challenge.

That's basically the main thing that's missing.  That issue should be resolvable.

I think the idea is, try to find the minimal generating set for groups Z_(p^k)* .

11:55 a.m.

************************************************************************************************

Can we rely on tracks to prove that, for example, any generator of (mod p^1) is also a generator for (mod p^2)?  We might be able to prove that it's a generator for (mod p^2) using the idea that we are not on any track, because the gcd of every element of (mod p^2) that is coprime to p is 1.  (We call the gcd=1 track the "coprime environment".)

Keep relying on these epiphanies to make progress!

The claim is:  If the generator g for p^1 does not lead to any tracks being entered other than the gcd=1 track, then since mod p^2, or more generally mod p^k, all of the numbers coprime to p^k in [0,p^k-1] are on the same track.  Thus, the generator g cannot form a new track by repeating a loop of elements within p^k without repeating all of the elements; all of the elements are on the same track.

The thing is, though, we have to use the fact that g is a generator to make this proof work.  What if g is not a generator for p^1?  Then does it work?  The argument is, if g is not a generator for p^1, what it does is, it enters a track.  It must.

Do an example?  What's an example, mod 23, of a non-generator, and what does it yield instead when exponentiated?

g=2

2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1

OK, 2 is a good example.

Does 2 cause us to enter a track??  I think the answer is, yes, but it's not a well-behaved track.  Maybe my theory about tracks is wrong!!  All of the elements generated are coprime to p, which is prime.  But it is still a sub-track of the main group.

I think some tracks are not fully generated.  Tracks still exist.  But not everything on a track, or on the coprime environment, will generate the *full* track.  To generate the full track, it needs to be a generator.

So that's the key insight...some non-generators generate *part of* the coprime environment, and, presumably, some non-generators for tracks generate *part of* certain tracks.

Does this damage my overall proof?  Don't try to prove the thing about generators for p^k.

What if there is no generator for some groups mod p^k?  Go look up that page about phi(p-1).

************************************************************************************************

12:13 p.m.

************************************************************************************************

https://www.quora.com/How-many-generators-does-the-group-mathbb-Z-125-have

Maybe my other resource was wrong?  Maybe it's actually, given Z+M*, phi(M), not phi(M-1).  That's the number of generators.

So the comment is, phi(p^k) > 0.  It's actually p^(k-1)*(p-1) = p^k - p^(k-1).  Great!

I will probably need to cite that Quora page!

Include a note in the final paper about the AI use; say that you asked a question about generators out of curiosity, and the final result did not yield anything that I used in the paper.

So the comment is, the number of generators is equal to the number of coprime elements.  Wait...that can't be right.  2 is coprime to 23, but not a generator of the group.

2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1

************************************************************************************************

Oh, the problem with that resource is, they mean (Z_m, +).  I'm concerned with (Z_m*, *).

I think the formula was wrong.  It seems to have disappeared from Wikipedia.  I think that ...

Nope!  There is a good source!

https://en.wikipedia.org/wiki/Primitive_root_modulo_n

It's under the section, "Finding Primitive Roots."

The number of primitive roots, if there are any, is equal to phi(phi(n)).  N is the modulus,

This page is good, too:

https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n

Under "cyclic case," it says:

The group Z_N* is cyclic if and only if N = 1, 2, 4, p^k, or 2*p^k, where p is an odd prime and k > 0.

Great!  If a group is cyclic, then it has a generator!  So p^k does have a generator, and we can compute how many of them using phi(phi(M)).  :D.

So we definitely *don't* need the proposition about every generator of Z_p* is a generator of Z_p^k*.  The generator count is just phi(phi(p^k)).  We're likely to be able to find one easily :).

12:40 p.m.

************************************************************************************************

So, the comment is, a non-generator will yield a sub-set of the coprime environment or the track.  It doesn't affect the proof I don't think.  It just means, if we use a value that is not a generator, we will not obtain the full track or coprime environment.

************************************************************************************************

************************************************************************************************

We avoid using values that are not generators.  A generator can generate a track or the coprime environment.  The claim is, every track has a genexrator, too.  We consider the number of elements in the track, and take phi of phi of that, and that's the number of generators for the track--I think that can be proved using the fact from the internet about phi(phi(M)).  You just say, it's a regular group, but with all the numbers multiplied by a certain constant.  E.g., 10*a (mod 100).  It's just a (mod 10), with the integer 10 multiplied to each element and to the modulus.

************************************************************************************************

12:48 p.m.

https://math.stackexchange.com/questions/976415/convergence-of-infinite-product-of-prime-reciprocals

Consider that article too.  I might want to include that sum to indicate that it is possible that generators is technically not in PTIME, even though it is very rare for an instance to come up where it can't be solved efficiently using simple guessing.

12:50 p.m.

I think the hardest part of the proof will be:  Proving that the expression of all the possible solutions to the square root problem is "small," i.e., that we can find a numerical upper bound on the number of solutions.  Note, each solution is written in a way that is polynomial in the size of M, the modulus.

************************************************************************************************

Make sure you prove the thing about the expression of the DL answers being of the form A (mod B), where A is an integer in [0, M-1] and B is an integer in [0, M-1] such that B|M.

************************************************************************************************

1:02 p.m.

Note, we should define "generator candidates" for both the coprime environment and tracks.  There are no generator candidates for tails.  The idea is, the "track value" should be a factor of the generator candidate, too.

 

7:29 p.m.

When you get the time and money:  Re-buy Mendelson, and try to formalize this proof in PA.