Academic Question about Cryptography

For discussions about security.
Post Reply
Message
Author
User avatar
mahaju
Posts: 487
Joined: Mon 11 Oct 2010, 07:11
Location: between the keyboard and the chair

Academic Question about Cryptography

#1 Post by mahaju »

http://rapidshare.com/files/437713784/F ... cation.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.
Attachments
Fast_multiplication.zip
(67.51 KiB) Downloaded 469 times

User avatar
Cust0dian
Posts: 28
Joined: Fri 22 Oct 2010, 11:26
Location: Russian Federation, St. Petersburg

#2 Post by Cust0dian »

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

User avatar
Flash
Official Dog Handler
Posts: 13071
Joined: Wed 04 May 2005, 16:04
Location: Arizona USA

#3 Post by Flash »

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

User avatar
mahaju
Posts: 487
Joined: Mon 11 Oct 2010, 07:11
Location: between the keyboard and the chair

#4 Post by mahaju »

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?

:)

User avatar
Cust0dian
Posts: 28
Joined: Fri 22 Oct 2010, 11:26
Location: Russian Federation, St. Petersburg

#5 Post by Cust0dian »

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

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.

Post Reply