Refactoring of primitive_root
#24883
Conversation
p into two patterns and made them independent as a function.
|
✅ Hi, I am the SymPy bot. I'm here to help you write a release notes entry. Please read the guide on how to write release notes. Your release notes are in good order. Here is what the release notes will look like: This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.13. Click here to see the pull request description that was parsed.
Update The release notes on the wiki have been updated. |
Once one primitive root g is found, the other primitive roots are represented by powers of g. In this case, the exponent and p-1 are relatively prime. Therefore, there is no need to perform power calculations to determine the primitive roots every time.
|
Benchmark results from GitHub Actions Lower numbers are good, higher numbers are bad. A ratio less than 1 Significantly changed benchmark results (PR vs master) Significantly changed benchmark results (master vs previous release) before after ratio
[2c3de5f4] [94fc2abc]
- 112±3ms 73.7±2ms 0.66 integrate.TimeIntegrationRisch02.time_doit(10)
- 108±2ms 70.2±0.9ms 0.65 integrate.TimeIntegrationRisch02.time_doit_risch(10)
Full benchmark results can be found as artifacts in GitHub Actions |
|
I'm not sure if |
|
thank you for comment. |
|
I wonder if it might be better still to leave the sorting for the public facing functions so the low-level can just return what's convenient and the higher level functions sort it if necessary. As long as it is canonical it need not be sorted for purposes of testing. |
|
Please consider whether sorting is necessary at this level. |
|
To begin with, So how about the following implementation?
|
I think that would be ok -- I don't work with ntheory much, however, and don't know what the preferences of someone would be. |
|
Thanks. I fixed it. |
no need for full extent of trailing
|
If the changes look ok to you, this is ready. |
|
thank you. |
|
Now that I look at it, I agree that the sorting of factors is not important since the g that is returned is incremented from small to large and simply has to pass a test with all factors. Thanks for your work on this. |
p into two patterns and made them independent as a function.
_primitive_root_prime_iterGenerates the primitive roots of
p. Once one primitive rootgis found, the other primitive roots are represented by powers ofg. In this case, the exponent andp-1are relatively prime. Therefore, there is no need to perform power calculations to determine the primitive roots every time._primitive_root_prime_power_iterGenerates the primitive roots of
p**e. Letg(0 < g < p) be the primitive root ofp. Ifpow(g+s*p,p-1,p**2)!=1, theng+s*pis primitive root ofp**e. There is always one integers(0 <= s < p) pergthat does not satisfy this condition, and the otherp-1are primitive roots. Thus, we findtotient(p)*(p-1)primitive roots ofp**2, which is consistent withtotient(totient(p**2)). The primitive roots ofp**3are all numbers congruent to the primitive roots ofp**2byp. The same is true forp**e(e > 3), which is consistent with thetotient(totient(p**e)). From the above, we see thatg+(k+m*p)*pis all of the primitive roots ofp**e. Wheregis primitive root ofp(0<g<p),0 <= k < p,0 <= m < p**(e-2),g**(p-1)+(p-1)*g**(p-2)*k*p % p**2 != 1._primitive_root_prime_power2_iterGenerates the primitive roots of
2*p**e. Ifgis the primitive root ofp**e, then the odd one ofgandg+p**eis the primitive root of2*p**e. Sincetotient(totient(2*p**e))=totient(totient(p**e)), this is all the primitive roots of2*p**e.References to other Issues or PRs
Brief description of what is fixed or changed
Other comments
Release Notes
smallestoption toprimitive_root