ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1132. Square Root

A little help from author
Posted by Michael Medvedev (KNU training center) 5 Nov 2001 13:45
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
Posted by Michael Medvedev (KNU training center) 5 Nov 2001 16:06
> 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
Posted by Michael Medvedev (KNU training center) 5 Nov 2001 17:31
>
> 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?
Posted by Czw's Brother 14 May 2004 18:02
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
Posted by liuchang 15 Jun 2004 20:08
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
Posted by Korduban [Kiev] 22 May 2005 18:11
Michael Medvedev (KNU training center) wrote 5 November 2001 13:45
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
Posted by Yu Yuanming 5 Jun 2005 21:11
(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
Posted by currently unnamed... 4 Apr 2006 11:27
The link is broken now...
Re: KISS method
Posted by Korduban [Kiev] 4 Sep 2006 23:45
chapter 5 (without subindexes) - sorting, exercise 25, the last one before chapter 5.1
Re: broken link
Posted by Rafail Ahmadisheff 26 Jul 2008 01:28
Try adding "www." at the beginning:
http://www.cacr.math.uwaterloo.ca/hac/
Re: A little help from author
Posted by qingyezhu 2 Oct 2011 19:13
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
Posted by luckysundog 27 Oct 2011 06:05
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)).