The time now is Sun 23 Nov 2014, 12:27
All times are UTC  4 
Author 
Message 
mahaju
Joined: 11 Oct 2010 Posts: 493 Location: between the keyboard and the chair

Posted: Fri 17 Dec 2010, 00:56 Post subject:
Academic Question about Cryptography Subject description: 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.
Description 

Download 
Filename 
Fast_multiplication.zip 
Filesize 
67.51 KB 
Downloaded 
291 Time(s) 

Back to top



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

Posted: 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



Flash
Official Dog Handler
Joined: 04 May 2005 Posts: 11156 Location: Arizona USA

Posted: 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.

Back to top



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

Posted: 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?

Back to top



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

Posted: 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 + (n1) + ... + 2 + 1)
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 n1 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





You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum You cannot attach files in this forum You can download files in this forum

Powered by phpBB © 2001, 2005 phpBB Group
