A little help from author
The solution is really hard enough - you must know the
serious number theory :-) :-) :-)
read a book Handbook of applied cryptography
at
http://cacr.math.uwaterloo.ca/hac/ Especcialy chapter 2 - mathematical background,
and the solution to the problem is written in chapter 3 -
subchapter about square root problem.
Author
To the author
Posted by
Li, Yi 5 Nov 2001 15:26
I've read the pdf files, then write the program as the
algorithm described in the file, and also "Time Limit
Exceeded"!
What must I pay attention for?
Help from author
> I've read the pdf files, then write the program as the
> algorithm described in the file, and also "Time Limit
> Exceeded"!
> What must I pay attention for?
1. Power opreration x^n - O(log n)
2. Evaluate Legandre symbol based NOT on factorization, but
in chapter 2 exist recursive algorithm (I havn't just the
chapter, but I'll try to see and will tell the page)
If some questions will arise, will try to answer. By the
way, you can post me your solution to medv@rambler.ru and I
will tell you the error (why time limit exceeded).
Medvedev Michael
Re: A little help from author
Posted by
snake 5 Nov 2001 16:45
The problem is really hard enough,
but the test data is really easy enough.
so the The solution is NOT really hard enough
Question for free
>
> The problem is really hard enough,
> but the test data is really easy enough.
> so the The solution is NOT really hard enough
>
>
Hello, free!
What is your solution, send me please it to medv@rambler.ru
I can for it send you my tests. You'll see that the tests
are big and good enough.
Author
I've already got ac before I saw this post. Thank you all the same
Posted by
Li, Yi 5 Nov 2001 18:28
Re: A little help from author
Posted by
Flyer 8 Nov 2001 16:29
You know, I've realized algorithm "Zessenhaus-Kantor", but
it writes Time-limit!!! This algorithm has O(log n). What
is your algorithm?
Re: Help from author
Posted by
HELLER 16 Apr 2002 01:32
> 2. Evaluate Legandre symbol based NOT on factorization, but
> in chapter 2 exist recursive algorithm (I havn't just the
> chapter, but I'll try to see and will tell the page)
Hmm, Legandre for 2 numbers = 1 or -1 (-1 ~ n-1), right?
If that is so, can i use Euler criteria? a^((n-1)/2)=(a/p) mod p
where (a/p) - Legandre symbol.
any one can tell me a easy way to solve it?
Re: any one can tell me a easy way to solve it?
Posted by
sloboz 16 May 2004 21:54
why don't you read the document posted by the author?
Re: To the author
The Important Hint:
Use longint to calculate.Because it use O((logn)^3) bit-operations.Another one,you may use Euler criteria to calulate Legendre.
KISS method
The solution is really hard enough - you must know the
serious number theory :-) :-) :-)
Simple deterministic method with complexity O(sqrt(N)) is described in "The Art Of Computer Programming" (exercise 5.25). It's just enough - my program accepted in 0.890 sec.
Re: KISS method
(exercise 5.25)? I can't find it. Can you tell me at which volumn and page(although the verson may be different)?
I am so interested in using search method to solve this problem...
Re: A little help from author
The link is broken now...
Re: KISS method
chapter 5 (without subindexes) - sorting, exercise 25, the last one before chapter 5.1
Re: A little help from author
url error??
Re: A little help from author
Posted by
Isidro 26 Oct 2011 00:46
Hi, I used the algorithm that is in the book you said, but I got TLE, can you help me?
Re: A little help from author
Do you speak about 3.34 algorithm from HAC book?
How do you find quadratic non-residue modulo p? I didn't search it randomly and use precompiled array of pairs (prime, some_non-residue (mod p)).