Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
December 20th, 2012, 03:20 PM
 ganterok
Registered User

Join Date: Dec 2012
Posts: 11
Time spent in forums: 3 h 31 m 30 sec
Reputation 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
December 20th, 2012, 03:43 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,218
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 51 m 46 sec
Reputation Power: 455
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)?
__________________
[code]Code tags[/code] are essential for python code!

#3
December 20th, 2012, 03:58 PM
 ganterok
Registered User

Join Date: Dec 2012
Posts: 11
Time spent in forums: 3 h 31 m 30 sec
Reputation 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
December 20th, 2012, 04:11 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,218
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 51 m 46 sec
Reputation Power: 455
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
December 20th, 2012, 04:23 PM
 ganterok
Registered User

Join Date: Dec 2012
Posts: 11
Time spent in forums: 3 h 31 m 30 sec
Reputation 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
December 21st, 2012, 05:38 AM
 mitakeet
I'm Baaaaaaack!

Join Date: Jul 2003
Location: Maryland
Posts: 5,538
Time spent in forums: 2 Weeks 4 Days 2 h 38 m 46 sec
Reputation Power: 243
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.
__________________

My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
Free code: http://sol-biotech.com/code/.
Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.

It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
--Me, I just made it up

The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
--George Bernard Shaw

#7
December 21st, 2012, 11:55 AM
 ganterok
Registered User

Join Date: Dec 2012
Posts: 11
Time spent in forums: 3 h 31 m 30 sec
Reputation Power: 0
Quote:
 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
December 21st, 2012, 12:29 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,218
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 51 m 46 sec
Reputation Power: 455
http://en.wikipedia.org/wiki/File:Codrii_dolna.jpg

Lovely picture but I do not understand "Dolna program".

#9
December 21st, 2012, 11:56 PM
 ganterok
Registered User

Join Date: Dec 2012
Posts: 11
Time spent in forums: 3 h 31 m 30 sec
Reputation 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
December 23rd, 2012, 02:53 AM
 ganterok
Registered User

Join Date: Dec 2012
Posts: 11
Time spent in forums: 3 h 31 m 30 sec
Reputation Power: 0
Somebody help me? : (

#11
December 23rd, 2012, 03:29 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,218
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 51 m 46 sec
Reputation Power: 455
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
December 23rd, 2012, 04:27 PM
 ganterok
Registered User

Join Date: Dec 2012
Posts: 11
Time spent in forums: 3 h 31 m 30 sec
Reputation Power: 0
Quote:
 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
December 23rd, 2012, 06:10 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,218
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 51 m 46 sec
Reputation Power: 455
With the further restriction that any code not in libc.o may NOT be used.

#14
December 23rd, 2012, 06:25 PM
 ganterok
Registered User

Join Date: Dec 2012
Posts: 11
Time spent in forums: 3 h 31 m 30 sec
Reputation Power: 0
Quote:
 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
December 23rd, 2012, 06:33 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,218
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 51 m 46 sec
Reputation Power: 455
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."

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Goldwasser-Kilian's and Atkin-Morain's algorithms