Discussion @ 1132. Square Root @ Timus Online Judge

Michael Medvedev (KNU training center) A little help from author [18] // Problem 1132. Square Root 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

Li, Yi To the author [6] // Problem 1132. Square Root 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?

Michael Medvedev (KNU training center) Help from author [4] // Problem 1132. Square Root 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

Li, Yi I've already got ac before I saw this post. Thank you all the same // Problem 1132. Square Root 5 Nov 2001 18:28

HELLER Re: Help from author [2] // Problem 1132. Square Root 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.

Czw's Brother any one can tell me a easy way to solve it? [1] // Problem 1132. Square Root 14 May 2004 18:02

sloboz Re: any one can tell me a easy way to solve it? // Problem 1132. Square Root 16 May 2004 21:54

why don't you read the document posted by the author?

liuchang Re: To the author // Problem 1132. Square Root 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.

snake Re: A little help from author [1] // Problem 1132. Square Root 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

Michael Medvedev (KNU training center) Question for free // Problem 1132. Square Root 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

Flyer Re: A little help from author // Problem 1132. Square Root 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?

Korduban [Kiev] KISS method [2] // Problem 1132. Square Root 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.

Yu Yuanming Re: KISS method [1] // Problem 1132. Square Root 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...

Korduban [Kiev] Re: KISS method // Problem 1132. Square Root 4 Sep 2006 23:45

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

currently unnamed... Re: A little help from author [1] // Problem 1132. Square Root 4 Apr 2006 11:27

The link is broken now...

Rafail Ahmadisheff Re: broken link // Problem 1132. Square Root 26 Jul 2008 01:28

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

qingyezhu Re: A little help from author // Problem 1132. Square Root 2 Oct 2011 19:13

url error??

Isidro Re: A little help from author [1] // Problem 1132. Square Root 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?

luckysundog Re: A little help from author // Problem 1132. Square Root 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)).

Discussion of Problem 1132. Square Root