Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Re:for p prime, B^(P-1)==1 (mod P), B^(P-2)==B^(-1) (mod P)

Posted by frkstyc at 2005-04-24 20:18:48 on Problem 2417
In Reply To:Re:for p prime, B^(P-1)==1 (mod P), B^(P-2)==B^(-1) (mod P) Posted by:uni at 2005-04-24 20:11:52

分解因数O((logN)^3)？不可能吧，除非是非常特殊的数。
LaMacchia有篇论文写的算离散对数要用Generalized Number Field Sieve，这个是目前已知最快的因数分解算法，复杂度是O(exp(1.9223 * (lnN)^(1/3) * (lnlnN)^(2/3)))，这个的阶比O((logN)^3)肯定要高，不算你可以算一下N->inf时的极限

Followed by:

Re:for p prime, B^(P-1)==1 (mod P), B^(P-2)==B^(-1) (mod P) (102) uni 2005-04-24 20:22:08
- Re:for p prime, B^(P-1)==1 (mod P), B^(P-2)==B^(-1) (mod P) (79) frkstyc 2005-04-24 20:26:32
  - Re:for p prime, B^(P-1)==1 (mod P), B^(P-2)==B^(-1) (mod P) (36) uni 2005-04-24 20:31:43
    - Re:for p prime, B^(P-1)==1 (mod P), B^(P-2)==B^(-1) (mod P) (49) frkstyc 2005-04-24 20:34:29
      - Re:for p prime, B^(P-1)==1 (mod P), B^(P-2)==B^(-1) (mod P) (13) Sinya 2010-04-20 08:51:51

Post your reply here:

Home Page Go Back To top