Showing posts with label binary expansion. Show all posts
Showing posts with label binary expansion. Show all posts

Wednesday, July 07, 2010

binary expansion in C# - converting BigInteger to binary form

This source code will do the job.
Add appropriate controls and fire the number: 174050332293622031404857552280219410364023488927386650641
and you'll get:
01110001100100101011100101011111111111001000110110100111100001100011000100000001000111101101011010110010010011001101110101010111001111111001011101111010000100011110011110010100100000010001
with a bunch of more noughts in front.
What a happy day. :)


using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Numerics;

namespace binaryexpansion
{
public partial class Form1 : Form
{

public Form1()
{
InitializeComponent();
}

private void button1_Click(object sender, EventArgs e)
{
BigInteger t = BigInteger.Parse(inputnr.Text);
selResult.Text = calcBinary(t);

//the line below would work if t was an integer - so nice and easy, but no dice with BigIntegers
//string t2 = Convert.ToString(t, 2);

}


private string calcBinary(BigInteger tee) {

BigInteger t = tee;
//4 times the length because it takes about 3 times the number of digits to write a number i binary form
int len = 4*(inputnr.Text).Length;

string fullnum= " ";
for (int i = len; i >= 0; i--)
{
int inum;

BigInteger num = (t >> i)&1;
if(num == 1){
//ugly but easy
inum = 1;}
else if(num == 0){
inum = 0;}
else{
inum=666;
}
fullnum = fullnum + Convert.ToString(inum);

}
return fullnum;

}
}
}

Saturday, June 06, 2009

Double and Add algorithm

Very much like the fast powering algorithm - binary expansion can be used to calculate Q= nP fast.
ex n=947 = 2^9+2^8+2^7+2^5+2^4+2^1+2^0

which means that 947P = P+2P+16P+32P+128P+256P+512P. Thats 9 doublings and 6 additions, much better than 946 additions....
if we allow subtraction as well (ternary expansion) its even better.

want to calculate nP?

algorithm:
1. input point P from E(Fp) and n>=1
2. set Q=P and R=Ø (point at infinity)
3. loop while n>0{
if n = 1 (mod2) set R= R+Q
set Q=2Q and n=n/2 (floor)}
4.return R (which equals nP)


I've now posted working sourcecode available at http://christelbach.com
(source code contained in master thesis)

for instance this:
//double and add algorithm
private BigInteger[] calculatenP(BigInteger x, BigInteger y, BigInteger n, BigInteger A, BigInteger modp)
{
BigInteger[] Q = { x, y };
BigInteger[] R = { 0, 0 };
while (n > 0)
{
BigInteger t = BigInteger.ModPow(n, 1, 2);
if ((t) == 1)
{
R = addPoints(Q[0], Q[1], R[0], R[1], modp);
}
Q = doublePoints(Q[0], Q[1], A, modp);
n = n / 2;
}
BigInteger[] resPoint = { R[0], R[1] };
return resPoint;
}


Look in the pdf file for the methods addPoints() and doublePoints()