> ...in the homework, it asks that we use k = 2, 3, 4, 5 for part 1.  
> I get valid results for k=2, which then narrow down with k=3,
> and 4, but I don't get any valid results for k=5.  Is that a problem?

Remember that these intervals are around "good" ratios for omega and m.  
When you incorporate more and more knapsack lengths, you gradually weed 
out more bad intervals (bad ratios).  But there should always be at 
least one good interval, because we expect that a ratio between omega and 
m actually exists.  So no, you should never run out of intervals, even if 
you consider all of the knapsack lengths.

> There are 26 rows in the problem, so i think Bi & ti should be 26 in length.

This depends on mu.  I think you happen to be right, but you should not
count on this.
  
The number of bits you consider at any time is mu bits.  mu is the log
(base 2) of the sum of all your public knapsack elements.  Why?  When  
encrypting, you consider a chunk of plaintext equal to the length of your
public knapsack (8 in this case).  For every '1' bit in that chunk of
plaintext, you add the corresponding knapsack value.  Refer to page 6 of
the reader.  The first chunk is

  1 0 0 0 1 0 0 1

This corresponds to the first, fifth, and eighth knapsack values
  
  1318 + 2428 + 284 = 4030
  
You add those together to get the first B, which is then represented in 15
bits (right column on page 6).
  
15 is mu, and you need 15 bits because if you had all 1s instead of the
10001001 pattern, you would need to add up all the ai values, and you
happen to need 15 bits to represent that sum.
  
> si should naturally be 8 bits in length, since it is the private knapsack.

That's right.  The private and public knapsacks are the same length.

> And when performing the ti - si step you should produce 8 bits in reverse
> order per row; one for each bit in si; Which would give me 208 bits (26 rows
> * 8 bits per row). See the note below for a more fitting answer
  
Ok the problem is that you're subtracting incorrectly.  What you will do
is something similar to the encryption process, but with the private
knapsack si.  Refer now to page 7.  You read in your 15 bits (because mu
is 15 in this case), and represent that in decimal: 4030, same as above.
Now you compute

  t = (omega * B) mod m
  
Note: you can ignore and skip the third column (B^(i) mod m).  In this
case,
  
  t = 2107

Now you start from the largest private knapsack value and try to subtract.
Whenever you can subtract a knapsack value without going negative, do so
and write a 1, otherwise you write a 0.

  subtract      result             z
  ===========   ======             ========
  2107 - 2005 = 102                       1
  102  - 1003 = negative!                01
  102  - 501  = negative!               001
  102  - 100  = 2                      1001
  2    - 22   = negative!             01001
  2    - 11   = negative!            001001
  2    - 6    = negative!           0001001  
  2    - 2    = 0                  10001001

Remember to work from least significant to most significant (right to
left).  The next 8 bits you get are added onto the right:

  3533 - 2005 = 1528               10001001       1
  1528 - 1003 = 525                10001001      11
  525  - 501  = 24                 10001001     111
  24   - 100  = negative!          10001001    0111
  24   - 22   = 2                  10001001   10111
  2    - 11   = negative!          10001001  010111
  2    - 6    = negative!          10001001 0010111
  2    - 2    = 0                  1000100110010111

When you are done, you will have a long string of bits.  Take them 7 at a
time and convert to their ascii equivs.

> When solving for omega inverse, the notes say to find an integer that
> satisfies 1 = omega * omegaInverse (modulo m). Exactly what gets
> modulo'd, and when? (omega * 1/omega) mod m will always equal 1 for any
> number, as will (omega mod m) * 1 / (omega mod m).
> So I'm a bit confused... how exactly do you solve for this?

First of all, it's not really 1/omega, because that wouldn't be a natural
number (most likely).  In this context, omega^-1 is another way of saying

"Find some natural number, say x, that when multiplied by omega modulo m,
yields one.  Instead of throwing another variable into the mix, we can
just let x be called omega^-1 because it's kinda like a reciprocal, but
with natural numbers."

For example, 

  13*2 mod 25 = 1

  omega    = 13
  omega^-1 =  2
  m        = 25

Hopefully that makes a bit of sense.  As to the calculation of it...

refer to http://www.cs.ucsb.edu/~kirbysdl/cs178/multinv.html

for one way to do it.  You can brute force it, but you'll need to do
something similar but with bigger numbers (i think) for another homework,
so just do it the "right" way.

> After looking at your sample solution from last year Mike, a question came
> to mind....It looks as if you have many different M, omega, and omega-1
> values for the same interval....is this possible?

yup.  Remember your M values range from the largest a to four times that
value.  So even though you're weeding out a lot of possibilities using the
four tests, you still will have a bunch of Ms that do work. Or at least,
it is likely that you will have more than one.

So in the end, you will get different s arrays (private knapsacks).
That's why he says choose any two... the point is that any of those should
work... so choose two at random and decrypt to convince yourself!

>    I was wondering if we were only supposed to perform the 3 tests on the
> intervals found using all 5 of the k intervals, or are we supposed to do the
> 3 tests on every potential interval we find for k = 2, 3, 4, and 5
> intervals?  Thank you.

The point of doing all these intersections is that as we include more a_i
knapsack elements, we're performing more stringent tests.  The point is
that the correct interval will be in the intersection of all a_i
intervals, but we only consider the first 5 because that should be enough
to weed out bad values.

Short answer: only look at the last set (when k=5).  In fact, only doing
the first interval for k=5 generally works for me (but you will have to
try other intervals if you don't get any good results for the first
interval).  

Exactly right.  And M starts at the largest `a' (public knapsack) value
and goes to 4 times the starting value.

See shamirExample.pdf on the class web site

On Fri, 9 May 2003, Ted Huffmire wrote:

> Omega is the integer you found
> to live in the interval when you
> multiplied the endpoints by M.
> You need to find the multiplicative
> inverse of Omega modulo M.
>
> See the following link for an explanation
> of the Euclidean method and source code in Java:
> http://www.math.ksu.edu/math791/monday/moddiv.html
>
> > Which two numbers do we use as input to calculate the multiplicative
> > inverse and the GCD?

> Can we just check to see if a omega inverse exists (ie
> gcd = 1).  It says on the assignment that we have to
> display our results in a table like in the notes.  Is
> it ok to not compute the inverse since we dont need it
> anyway (or am I missing something and we do need it)
> and just leave that column in the table blank.

1) It's probably expected by Konheim, so I'd do it
2) It's around 15 lines of code, so I'd do it
3) you need it anyway in future homeworks, so I'd do it
4) Continuing from above, you might want to modularize your code so it's
easier to #include in your next homeworks.

Ted's right.  While this isn't the way I do it, you can probably still do
it efficiently.  Remember to not actually compute all the different
possibilities, but rather stop the current iteration and "continue" when
you detect an empty intersection.

for all a_0
  for all a_1
    compute the a_0, a_1 intersection
    if it fails
      continue
    else
      for all a_2
        compute...

... or something like that. YMMV, HTH, etc.

--Mike

(Ted please confirm that I'm not on crack).

On Thu, 8 May 2003, Ted Huffmire wrote:

> Date: Thu, 08 May 2003 16:41:51 -0700
> Subject: Re: project 6 program 1
>
> No you won't have to take thousands of years.
>
> Take a look at the pseudocode:
>
> http://www.cs.ucsb.edu/~konheim/CS178/KnapProg.pdf
>
> k=5 means you have 5 nested loops.
> there will be a loop for a0, a1, a2, a3, and a4.
> For aj's loop you try 0 to 0 + epsilon,
> 1/aj to 1/aj plus epsilon, ..., k/aj to k + epsilon, ...
> 1 - 1/aj to 1 - 1/aj + epsilon.
>
> btw, for modular division, see the following link:
>
> http://www.math.ksu.edu/math791/monday/moddiv.html
>
> Ted
>
> >
> > I have been programming program 1 and came to a problem.  To test for
> > (for example) k = 5, does that mean we will have 5 nested loops of
> > size 638, 3578, 971, 1942, 1388?  If this is the case then our program
> > will have to run through 638*3578*971*1942*1388 loops which is
> > 5974738975246624 loops!  This program will run for thousands of
> > years!!  Am I doing something wrong?  Thanks.
>

Here's another way of thinking about it a.k.a. how i did it. Don't nest all the for loops! Ok, first of all, we're gonna follow shamirExample. Go to page 3. Let's say we have all of the a_0, a_1, a_2, ... intervals computed. These are the things at the top of the page. You don't have to precompute them all, but it will be easier to understand this way. Example: a_0 is 638, so we'll have 637 intervals for a_0. Typo: All of the a_2 intervals will have an exponent of -5 (the first is incorrectly listed as -6) Having computed the individual intervals, we now start the intersections. The first table is "Intervals Determined by 2 Public Knapsack Lengths." s'like .. start with a_0, a_1 intersections. in a doubly nested for loop, compute all the intersections and store the nonempty results into a_01. Now we're going to compute "Intervals Determined by 3 Public Knapsack Lengths." So some people were wailin' ... this will be a nested for loop that runs for a total of 466*354*130 iterations! However... Consider three intervals (0,2), (3,5), (1,6). First we compute the intersection of the first two. It's empty! We know that the intersection of an enpty interval and any interval (like 1,6 in this case) is also empty, so we can toss this case away. This means whenever we have an empty interval, we don't have to ever consider it again. Notice that we've already found all the nonempty a_0,a_1 intersections though. So instead of finding all the empty things again, just use what we already have. Instead of finding intersections for a_0, a_1, a_2, we do intersections between a_01 and a_2. Store the result in a_012. Simple! Now we're doing 4 Knapsack Lengths. Like above, we reuse what we already know, so we're actually intersecting a_012 and a_3. Same sort of thing for 5 Lengths. Notice that each time, the number of possibilities from the last iteration is decreasing. a_01 is 9, a_012 is 4, and a_0123 is 2. So it IS pretty efficient. Notice each step involves a double nested for loop because you must still exhaustively compute all the intersections between what we've already seen (like a_012), and what we're adding (like a_3). If you're clever, you can wrap each of these in a third nested for loop. Then for any number of "Public Knapsack Lengths," you'll have the same set of 3 nice happy for loops for computing intersections. (Cleverness won't get you more points, so leave that to the end).

> are you planning to post any notes on hw6 on your web site?

http://www.cs.ucsb.edu/~kirbysdl/cs178-2002/hw6ci2002
http://www.cs.ucsb.edu/~kirbysdl/cs178-2002/hw6ci2002.rawoutput

I will, like always, post questions and answers as I get them.  Remember
to address both TAs!