Home

Miller-Rabin prime test in Java

Details: Written by Pham Ngoc Hai

A simple Miller-Rabin prime number test I wrote in Java.

Along with this method I implemented isWitness as well as the modulo power by bit shifting method.

Feel free to comment ;)

=================

Update:

Someone requested for myBigRanNum and FactorOfTwo, I put them here as well, enjoy.

=================

[code]public static boolean MillerRabin(BigInteger n, int k){

        BigInteger a;
        BigInteger m = n.subtract(BigInteger.ONE);
        boolean isPrime = true;

        if (n.compareTo(BigInteger.ONE) == 0) return false;
        if (n.mod(BigInteger.valueOf(2)).intValue() == 0) return false;

        for (int i = 0; i < k; i++) {
            a = myBigRanNum(MAX_BIT);
            if (a.compareTo(m) > 0) a = a.mod(m);
            if (a.compareTo(BigInteger.ZERO) == 0) a = BigInteger.ONE;

            if (isWitness(a, n)) return false;
        }
        return isPrime;

}

public static boolean isWitness(BigInteger a, BigInteger n) {
        int s;
        BigInteger apow;
        BigInteger firstEqua, secondEqua;
        BigInteger m = n.subtract(BigInteger.ONE);
        BigInteger d;
        s = FactorOfTwo(m);
        d = m.divide(BigInteger.valueOf((int)Math.pow(2, s)));

        firstEqua = ModExpo(a, d, n);
        if (firstEqua.intValue() == 1 || firstEqua.compareTo(m) == 0 ) return false;

        for (int r = 0; r < s; r++) {
            apow = d.multiply(BigInteger.valueOf((int)Math.pow(2, r)));
            secondEqua = ModExpo(a, apow, n);
            if (secondEqua.intValue() == -1 || secondEqua.compareTo(m) == 0) {
                return false;
            }
        }
        return true;
}

public static BigInteger ModExpo(BigInteger aBigInt, BigInteger pow, BigInteger n) {
        BigInteger e = pow;
        BigInteger a = aBigInt;
        BigInteger result = BigInteger.ONE;
        while (e.compareTo(BigInteger.ZERO) > 0 ) {
            if (e.and(BigInteger.ONE).compareTo(BigInteger.ONE) == 0 ){
                result = (result.multiply(a)).mod(n);
            }
            e = e.shiftRight(1);
            a = (a.multiply(a)).mod(n);
        }
        return result;
}

public static int FactorOfTwo(BigInteger aNumber) {
        int i = 0;
        BigInteger myNumber = aNumber;
        BigInteger myRemainer;
        while (true) {
            myRemainer = myNumber.mod(BigInteger.valueOf(2));
            if (myRemainer.compareTo(BigInteger.ZERO) != 0 ) break;
            myNumber = myNumber.divide(BigInteger.valueOf(2));
            i++;
        }
        return i;
}

public static BigInteger myBigRanNum(int numBits) {

        //We only deal with positive number here

        BigInteger aBigInterger = new BigInteger(numBits, aRand);
        aBigInterger = aBigInterger.abs();
        return aBigInterger;
}[/code]

filezilla-3.0.3.ebuild

Details: Written by Pham Ngoc Hai

net-ftp/filezilla/filezilla-3.0.3.ebuild

This is an ebuild for FileZilla 3.0.3, I also posted it at https://bugs.gentoo.org/attachment.cgi?id=136034

[code]# Copyright 1999-2007 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
# $Header: $
WX_GTK_VER="2.8"
inherit eutils multilib autotools wxwidgets
MY_PV=${PV/_/-}
MY_P="FileZilla_${MY_PV}"
DESCRIPTION="FTP client with lots of useful features and an intuitive interface"
HOMEPAGE="http://filezilla-project.org/"
SRC_URI="mirror://sourceforge/${PN}/${MY_P}_src.tar.bz2"
RESTRICT="mirror"
LICENSE="GPL-2"
SLOT="0"
KEYWORDS="~alpha ~amd64 ~ppc ~ppc64 ~sparc ~x86"
IUSE=""
RDEPEND=">=x11-libs/wxGTK-2.8.4
>=net-libs/gnutls-1.6.1
net-dns/libidn
>=sys-devel/libtool-1.4"
DEPEND="${RDEPEND}
>=sys-devel/gettext-0.11"
S="${WORKDIR}"/${PN}-${MY_PV}
pkg_setup() {
    if use unicode; then
        need-wxwidgets "unicode"
    else
        need-wxwidgets "gtk2"
    fi
}
src_compile() {
    WXRC="/usr/bin/wxrc-2.8" \
    econf --with-wx-config="${WX_CONFIG}" \
        || die "econf failed"
    emake || die "emake failed"
}
src_install() {
    emake DESTDIR="${D}" install || die "emake install failed"
    doicon src/interface/resources/FileZilla.ico || die "doicon failed"
    make_desktop_entry ${PN} "FileZilla" FileZilla.ico
    dodoc AUTHORS ChangeLog NEWS
}[/code]

AVISPA, SPAN on Gentoo

Details: Written by Pham Ngoc Hai

So far, AVISPA is not in the portage tree (of course) and there's no overlay that has this app. So you have to download the app from AVISPA web site http://www.avispa-project.org

AVISPA is only available as precompiled 32bits bianary, so you have no choice but to download and install it manually (you need to register to download).

Once downloaded, just extract it to a directory your home:

[code]cd ~

tar xvzf avispa-package-1.1_Linux-i686.tgz[/code]

The precompiled 32bits SPAN does not work on x86_64 arch, if you run it, you will get something like:

[code]./span: error while loading shared libraries: libtk8.4.so: wrong ELF class: ELFCLASS64[/code]

Then you have to build it

To build SPAN, you'll need dev-lang/tk and dev-lang/ocaml, so emerge them:

[code]emerge -av dev-lang/tk dev-lang/ocaml[/code]

Now you need to get SPAN from here http://www.irisa.fr/lande/genet/span/span-1.1-source.tar.gz

Put it somewhere you can remember, for example ~/Desktop

Now extract span to a directory, let's say ~/

[code]cd ~

tar xvzf span-1.1-source.tar.gz[/code]

You'll have a dicrectory named span

[code]cd span

make[/code]

If it complains, then you need to set following environment variable:

[code]export AVISPA_PACKAGE=~/avispa-1.1

export SPAN=~/span[/code]

Once compiled, you're ready to run SPAN:

[code]./span[/code]

If span cannot find OFMC, ATSE, TA4SP... libs or config files, just copy the respective directories and files from ~/avispa-1.1/bin/backends to ~span/bin/backends

I'll make an ebuild for SPAN once I have time.

About Linux Rapidshare Grabber

Details: Written by Pham Ngoc Hai

Linux Rapidshare Grabber is tool for rapidshare member to download multiple rapidshare links. It runs in Linux and I have no plan to port it to Windows.

This will work only if you have a valid rapidshare account. If you dont, this tool is NOT for you.

And yes, it's open source!
Features:
- Resumable
- Download rapidshare folder/linklist
- Multiple concurrent files download / multiple concurrent parts per file

- Support proxy

The project site is at SoureForge

http://lrg.sourceforge.net/

Project summary:

http://sourceforge.net/projects/lrg/

You can download it here:

http://sourceforge.net/project/platformdownload.php?group_id=235420&sel_platform=9781