mersenneforum.org > Math Basic questions about modular roots
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2019-02-10, 10:30 #1 mathPuzzles   Mar 2017 111102 Posts Basic questions about modular roots We have an nth root of unity modulus a composite C. So $$a^n \equiv 1 \mod C, a\ne 1$$. Since $$a$$ is a root, so is $$a^2, a^3, a^4 \ldots$$ until the list cycles back to $$a$$ in at most $$n$$ entries. Since C is composite, the roots in that list are not all the possible roots, there can be another root $$b$$ which is not in that enumerated set, and it has its own list of derivative roots $$b, b^2, b^3, b^4 \ldots$$. What is the vocabulary word that discribes these kinds of sets? Something like "derived roots of a" or something. If n is 2, you could probably use the word "conjugates" for a pair of roots. I want to be able to write something like "If $$C=pq$$ then we need one characteristic root from two different (superconjugate sets??) to be able to enumerate all of the n'th roots of unity." without making up my own vocabulary and overly amusing real mathematican readers. Second question is regards to the number theory of roots itself. I've seen it stated in descriptions of factoring algorithms that if we have two such sets of roots and do indeed know a characteristic root from each set, then GCD(a-b, C) will reveal p or q as a factor of C. I can test this experimentally, but I have not been able to derive it. What's the strategy? I suspect it's very elementary and I just have a mental block about the direction to take to crack it. Thanks for any help!
 2019-02-10, 14:43 #2 Dr Sardonicus     Feb 2017 Nowhere 22·769 Posts I suggest looking here.
2019-02-12, 23:10   #3
mathPuzzles

Mar 2017

2×3×5 Posts

Quote:
 Originally Posted by Dr Sardonicus I suggest looking here.
Thanks for the hint!
So in my problem it seems like my roots a and b are called "primative modular n-th roots of unity" and I would refer to a sets as "a multiplicative ring of derived modular n-th roots".

How would I state the fact that the two rings share 1, but are otherwise disjoint? ie, a and b are special in that one is not a power of the other (or it'd be in that ring).

Next I need to tackle the GCD(a-b, C) finding a factor of C conjecture. I'm no longer certain it's true, and maybe it just works in some random cases (common when C is small)

Thanks!

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 0 2017-01-19 20:22 Nick Number Theory Discussion Group 0 2017-01-07 13:15 Nick Number Theory Discussion Group 1 2016-10-21 22:21 schwerlin Information & Answers 6 2015-01-20 19:26 VictordeHolland Information & Answers 5 2013-09-04 01:47

All times are UTC. The time now is 21:12.

Thu Apr 9 21:12:52 UTC 2020 up 15 days, 18:45, 1 user, load averages: 1.94, 1.66, 1.58

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.