### Thread: Goldwasser-Kilian's and Atkin-Morain's algorithms

Page 1 of 2 12 Last
1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
11
Rep Power
0

#### Goldwasser-Kilian's and Atkin-Morain's algorithms

Hello , people!
Immediately apologize for my english, because I know the language is very bad!

I need help in the implementation of these two algorithms (Goldwasser-Kilian, Atkin-Morain) based on the test using elliptic curves (Testing Primality)... rather their immediate implementation. I have problems with discrete mathematics, so I cann't understand the algorithm. Both algorithms are not large and didn't seem very complicated, but ** discrete mathematics does not leave me a chance to solve this problem.
On our forums all asking for money for this work ... but I have no money as a scholarship to our university about \$ 40 :)
I ask for your help with this problem in C / C + + .... i have only 2 days...

I hope for your help, very grateful for the earlier,
Ganter.
2. Please post some sort of effort. What size numbers do you need to deal with? Do you need the gnu multi-precision library (or other)?
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
11
Rep Power
0
The number of large orders. Required to perform regardless of the library program modules and their source. The meaning of the job - for example, the test for large numbers to analyze the time complexity and the efficiency of these algorithms. I can do the analysis, but the code itself - no
4. This project looks immense with a 2 day time frame.

What is your major? If you're a computer science major and don't know how to write computer programs most people who read this forum will vehemently oppose helping you. If you're a math major and somehow this programming question slipped in to your homework you might get help.

The gmp, and some computer languages already implement Miller-Rabin test (needed to find probable primes, I believe) and arbitrary precision numbers. Something isn't right. Why are these disallowed?
5. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
11
Rep Power
0
My specialty is a specialist in information security (technical security systems and information security) This task was given to me this afternoon on cryptology (compulsory subject) However, I do not do programming, but the teacher gave this assignment, saying that there is nothing complicated about it over there O_o.
I can not quite understand the task correctly, translating it word for word:
Explore algorithms for primality testing:
1) Test the simplicity
Goldwasser - Killian
Atkin - Moraine
2) Run a prototype implementation of a software system providing
conduct numerical experiments to analyze the time complexity of these algorithms
3) 6. Make a report. Submit a report in print and online
form on a flash drive. As an application to the electronic form lead
executed regardless of the application modules and libraries of their source code
6. I suspect you are over analyzing the problem. Since you are not a programmer AND your major has nothing to do with programming I expect your instructor is not expecting you to solve the problem with programming. Ask for more information.
7. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
11
Rep Power
0
Originally Posted by mitakeet
I suspect you are over analyzing the problem. Since you are not a programmer AND your major has nothing to do with programming I expect your instructor is not expecting you to solve the problem with programming. Ask for more information.
Asked the teacher. He said that the problem be solved Dolna program, but gave another 5 days to complete ... The bottom line is - the program that I have ever had to write at "Hello World" ... learn enough basics of programming languages ​​for writing 5 days + write in my view is not possible ... Please help ... If necessary I will pay, because it will solve my thesis evaluation.
P.S. In Russia, a normal situation when a professional profile given the task of completely different .... the last day ... and the need to always carry it out ...
8. http://en.wikipedia.org/wiki/File:Codrii_dolna.jpg

Lovely picture but I do not understand "Dolna program".
9. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
11
Rep Power
0
"Lovely picture but I do not understand "Dolna program"."
Oh, sorry, it's "Lost in Translation": D. The problem to be solved to programmatically :)
10. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
11
Rep Power
0
Somebody help me? : (
11. Your project is due today + 5 = Friday or so. I might try to write the program in j. It has both these features: extended integers and built in Miller-Rabin primality testing. Time and space to evaluate a j sentence are also easily determined.
J implements Iverson notation, which isn't algebra, although I can often write sentences which read almost like English.

Also, any program resource use statistics you get will depend strongly on the extended precision implementation and may not help at all with predicting the polynomial time of your algorithm.
12. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
11
Rep Power
0
Originally Posted by b49P23TIvg
Your project is due today + 5 = Friday or so. I might try to write the program in j. It has both these features: extended integers and built in Miller-Rabin primality testing. Time and space to evaluate a j sentence are also easily determined.
J implements Iverson notation, which isn't algebra, although I can often write sentences which read almost like English.

Also, any program resource use statistics you get will depend strongly on the extended precision implementation and may not help at all with predicting the polynomial time of your algorithm.
I'm sorry, I said I did not have very good English) I do not understand whether the program will execute those two algorithms that I mentioned .... but even if it does not suit me J. Execution condition С/С++/С# ...
I would be very grateful if you could implement it in which any of these languages ​​(
13. With the further restriction that any code not in libc.o may NOT be used.
14. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
11
Rep Power
0
Originally Posted by b49P23TIvg
With the further restriction that any code not in libc.o may NOT be used.
Not quite understand what that means) Your message translated, and what it means not to understand) libc as I understood it is a standard library of C language family. But I did not understand what it means to "limit the use of other code not from the library"
Once again I apologize for my English ... I teach only one year, but if you use Google translator not learn never, so I apologize for the mistakes.
15. In post 3 you said
"The number of large orders. Required to perform regardless of the library program modules and their source."

This means "determine the primality of a 40 digit number". And "the code must be in a c language (or derivative) and use no libraries other than the standard library provide with c."
Page 1 of 2 12 Last