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

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?

> 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

The problem is really hard enough,
but the test data is really easy enough.
so the The solution is NOT really hard enough

>
> 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

 You know, I've realized algorithm "Zessenhaus-Kantor", but
it writes Time-limit!!! This algorithm has O(log n). What
is your algorithm?

> 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.

why don't you read the document posted by 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.

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.

(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...

The link is broken now...

chapter 5 (without subindexes) - sorting, exercise 25, the last one before chapter 5.1

Try adding "www." at the beginning:
http://www.cacr.math.uwaterloo.ca/hac/

url error??

Hi, I used the algorithm that is in the book you said, but I got TLE, can you help me?

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)).