Puppy Linux Discussion Forum Forum Index Puppy Linux Discussion Forum
Puppy HOME page : puppylinux.com
"THE" alternative forum : puppylinux.info
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

The time now is Sun 21 Sep 2014, 20:31
All times are UTC - 4
 Forum index » Off-Topic Area » Security
Academic Question about Cryptography
Post_new_topic   Reply_to_topic View_previous_topic :: View_next_topic
Page 1 of 1 Posts_count  
Author Message
mahaju


Joined: 11 Oct 2010
Posts: 493
Location: between the keyboard and the chair

PostPosted: Fri 17 Dec 2010, 00:56    Post_subject:  Academic Question about Cryptography
Sub_title: Abou the Mathematical background related to Cryptography
 

http://rapidshare.com/files/437713784/Fast_multiplication.pdf

I would like to discuss some aspects of these notes
First question is, in page 4 what does does it mean by: "The stuff in parenthesis doesn't amount to much (though it is fun to think about how much there is)."

And also, the number of steps for multiplication is 2n^2. i think it should be more. Could anyone please explain this to me?

Thanks in advance.
Fast_multiplication.zip
Description 
zip

 Download 
Filename  Fast_multiplication.zip 
Filesize  67.51 KB 
Downloaded  283 Time(s) 
Back to top
View user's profile Send_private_message 
Cust0dian


Joined: 22 Oct 2010
Posts: 28
Location: Russian Federation, St. Petersburg

PostPosted: Fri 17 Dec 2010, 19:58    Post_subject:  

Good day, sir.

This algorithm is also called "long multiplication". So, let's say you want to multiply 2938 (call it "a" number) and 3547 (call it "b" number).

Also, remember that
2938 = 2000 + 900 + 30 + 8
3547 = 3000 + 500 + 40 + 7
Let's take only digits from every number, but remember its position (how many zeros behind the digit), then:
2938 consists of 2, 9, 3, 8 (notation in the article a_4, a_3, a_2, a_1)
3547 — 3, 5, 4, 7 (b_4, b_3, b_2, b_1)


Multiplication part: each digit of one number multiplies on all digit from the second number. It is (n numbers of a) * (n numbers of b). Since we are talking about numbers with the same number of digits, n numbers of a = n numbers of b, so we need n^2 number of steps in multiplication part of algorithm.


Addition part:
First, why "the stuff in parenthesis" doesn't really matter: I don't know. In this example full calculation gives the 10 421 086, and calculation without steps in parentheses — 7 949 536. The difference is 25% — it DOES matter.

Second, you can't get n^2 steps without that steps in parentheses, you'll get something less than n^2. For this step look into columns method of addition and assume you have to remember and add one more number on each step. And still, very first digit of the first multiplication step will be the rightmost in the answer, we have nothing to add to it. So, my opinion, that number of addition steps will be (n^2 - 1) (= 2 + 3 + ... + n + (n - 1) + ... + 2 + 1), then total number of steps

2n^2 - 1

Really hope, this will help you
Back to top
View user's profile Send_private_message 
Flash
Official Dog Handler


Joined: 04 May 2005
Posts: 11069
Location: Arizona USA

PostPosted: Sat 18 Dec 2010, 00:09    Post_subject:  

Perhpas the author of the fast multiplication article meant that the stuff in parentheses doesn't matter for the purposes of a discussion about cryptography. Confused
Back to top
View user's profile Send_private_message 
mahaju


Joined: 11 Oct 2010
Posts: 493
Location: between the keyboard and the chair

PostPosted: Sat 18 Dec 2010, 07:30    Post_subject:  

Thank you for your replys

@Flash: I am still not sure what it means but I don't think that's what the author meant

@Cust0dain: Good day to you too sir
Perhaps the extra 1 operation can be attributed to a possible carry over from the extreme last digit? for example, if the last digit was a 9 and had a carry (of say 2), then it would still give out a carry which, although just need to be added to zero, would in fact increase the total number of digits in the final answer

But I am still not sure about this
What are your views?

Smile
Back to top
View user's profile Send_private_message 
Cust0dian


Joined: 22 Oct 2010
Posts: 28
Location: Russian Federation, St. Petersburg

PostPosted: Sat 18 Dec 2010, 10:40    Post_subject:  

mahaju wrote:
... it would still give out a carry which, although just need to be added to zero, would in fact increase the total number of digits in the final answer


I was counting it as last one addition step (2 + 3 + ... + n + (n-1) + ... + 2 + 1) Smile

Well, I'm looking at it now and thinking what if author count addition of all digits to zero? Like this one last step that we were talking about. Than, without carries, we'll have exctly n^2 steps.

If we count those steps in parentheses, we'll have (in worst case) 2 * (SUM from n=1 to n-1 of n) more steps (1 + 2 + ... + (n - 1) + (n - 1) + ... + 2 + 1), wich, as you can see is n less than n^2.

So, in case of such interpretation of this algorithm, it has (3n^2 - n) steps.
Back to top
View user's profile Send_private_message 
Display_posts:   Sort by:   
Page 1 of 1 Posts_count  
Post_new_topic   Reply_to_topic View_previous_topic :: View_next_topic
 Forum index » Off-Topic Area » Security
Jump to:  

Rules_post_cannot
Rules_reply_cannot
Rules_edit_cannot
Rules_delete_cannot
Rules_vote_cannot
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0556s ][ Queries: 12 (0.0053s) ][ GZIP on ]