Thursday, May 24, 2012

Simulation not starting in ISE Design Suite and ISIM

I was doing vhdl exercise using ISE design suite, while simulating, I faced several times that when I press start, nothing happen, I see run all displayed in the console, but nothing happens.

after spending some time on this, I found out to overcome this issue, I need to run the synthesize then sun the simulation again, this usually solves this issue for me.

Wednesday, May 16, 2012

Wordpress and Live writer bug

I had some html code in an entry I am posting in wordpress, I uploaded it using windows live writer, the post contains some html code for iframe tag. The funny thing is after publishing the post, the iframe tag is converted somewhere in the middle to <a> tag Smile

Original post html

&lt;iframe src=&quot;../common/Options.htm&quot; width=&quot;100%&quot; frameborder=&quot;0&quot;
  <br />scrolling=&quot;no&quot;&#160; marginwidth=&quot;1&quot;

  <br />marginheight=&quot;1&quot; height=&quot;100%&quot; name=&quot;CardOptions&quot; allowtransparency=&quot;true&quot;&gt;&lt;/iframe&gt;

 

Posted HTML

<a href="http://../common/Options.htm">http://../common/Options.htm</a></p>

Adding transparent frame

To add a transparent frame to an html page, to have the same background of the page

Set the background of the frame body to transparent

<body style="background-color:transparent">

in the page, add the following to the iframe tag

allowtransparency="true"

<iframe src="../common/Options.htm" width="100%" frameborder="0"
scrolling="no"  marginwidth="1"
marginheight="1" height="100%" name="CardOptions" allowtransparency="true"></iframe>

Wednesday, May 9, 2012

Miller Rabin primality test

I had exercise to implement Miller Rabin primality test

According to my text book, the test algorithms was as following

image

Test (n)

1. Find integers k,q,d with K>0, q odd, so that (n-1 = 2^k * q);

2. Select a random integer a,1<a<n-1;

3. if a^q mod n = 1 then return probably prime;

4. for j = 0 to k-1 do;

5. if a^2jq mod n = n-1 then return probably prime;

6. return not prime;

I also found another way of the algorithm in http://rosettacode.org/wiki/Miller-Rabin_primality_test as following

Input: n > 2, an odd integer to be tested for primality;
k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
LOOP: repeat k times:
pick a randomly in the range [2, n − 1]
xad mod n
if x = 1 or x = n − 1 then do next LOOP
for r = 1 .. s − 1
xx2 mod n
if x = 1 then return composite
if x = n − 1 then do next LOOP
return composite
return probably prime


When I tried both in  C#, both worked as expected



//textbook
public static bool IsProbabilyPrime(BigInteger n, int k)
{
bool result = false;
if (n < 2)
return false;
if (n == 2)
return true;
// return false if n is even -> divisbla by 2
if (n % 2 == 0)
return false;
//writing n-1 as 2^s.d
BigInteger d = n - 1;
BigInteger s = 0;
while (d % 2 == 0)
{
d >>= 1;
s = s + 1;
}
for (int i = 0; i < k; i++)
{
BigInteger a;
do
{
a = RandomIntegerBelow(n - 2);
}
while (a < 2 || a >= n - 2);

if ( BigInteger.ModPow(a,d,n) == 1) return true;
for (int j = 0; j < s - 1; j++)
{
if (BigInteger.ModPow(a,2*j*d,n) == n - 1)
return true;
}
result = false;
}
return result;
}

//rosettacode.org
public static bool IsProbablePrime(this BigInteger source, int certainty)
{
if (source == 2 || source == 3)
return true;
if (source < 2 || source % 2 == 0)
return false;

BigInteger d = source - 1;
int s = 0;

while (d % 2 == 0)
{
d /= 2;
s += 1;
}

RandomNumberGenerator rng = RandomNumberGenerator.Create();
byte[] bytes = new byte[source.ToByteArray().LongLength];
BigInteger a;

for (int i = 0; i < certainty; i++)
{
do
{
rng.GetBytes(bytes);
a = new BigInteger(bytes);
}
while (a < 2 || a >= source - 2);

BigInteger x = BigInteger.ModPow(a, d, source);
if (x == 1 || x == source - 1)
continue;

for (int r = 1; r < s; r++)
{
x = BigInteger.ModPow(x, 2, source);
if (x == 1)
return false;
if (x == source - 1)
break;
}

if (x != source - 1)
return false;
}

return true;
}