Largest factor

Some code to extract the largest factor of an integer, in Pari/GP

x=factor(v);y=matsize(x);x[y[1],1]

Party over radio

Small FM radios can be purchased for as little as two dollars (for example, search for FM radio at froogle and sort by increasing price). Imagine a dance party where everyone is given a headset to wear, and a local FM transmitter (either in the room or perhaps a FM station), and the dance party takes place essentially in silence with everyone listening to the same station.

Part of the motivation for this is to get around noise laws and how late parties are allowed to go.

Smooth plus delta

Represent a number by a smooth factorization plus (or minus?) a delta less than the largest factor.

Sawfish alt-tab

Sawfish behaves alt-right-tab and alt-left-tab behave slightly differently; alt-right-tab leaves the window name floating in the center of the screen, alt-left-tab does not.

Random Word generator

Dai uzen ehoo lotreersipeenk lo i ahupepy ignurde zaj cunai ashi grimp ye i obre hungo hai cistelf a o rikefroo islemoclo sla ursen end kitroong a tho dijuji. A ers utunpob bling ormolt zu ocalp crajulti nengicroc wel tronsu toor obecradait plo ep ni plulaistutang tac ert stoonkimi a uhalpo itwomuc zujyplospink i azocterdeeg.

contineu a not word

"contineu" is in the linux /usr/share/dict/words as a correctly-spelled word.

Failure Java gcc-4.0.1 compile

w3c.jar:1: error: Class or interface declaration expected. PK^E^F

1 error make[4]: *** [libw3c_gcj_la-w3c.lo] Error 1

(Giving up by disabling gcj compililation, for now.)

170 factorial

170! is the highest factorial you can calculate using standard double-precision floating point.

Userland AFS

If one had a microkernel operating system, and the filesystem "modules" ran in userland instead of kernel space, one in principle wouldn't even have to be root to have AFS; in stark contrast to having to go so far as to recompile the kernel to get AFS for some versions of Linux. Such is the appeal of non-monolithic kernels.

Language of matched parentheses

Given bitwise data, how can one encode it in the language of matched parentheses (possibly different types of parentheses). We seek a mapping function from bits to tree structures.

failure

If you enter failure into Google and hit the jISuDrup (or equivalent if your language preference isn't Klingon), you get Biography of President George W. Bush. I have no problems in propagating the meme.

blogger cleaned up SEO

When following the "Next Blog" buttons at the top, one no longer get tons of Search Engine Optimization pages.

printing into notebook

Printing directly into a notebook could be solved by a handheld scanner (not flatbed) like device. The key idea is the laser computer-vision-powered location technology that powers modern optical mice. Use the camera to determine where you are on the page and determine whether to drop ink, tonor, high-powered laser to burn the page, at that location. The printer need not be as wide as the page; once can go up and down "painting" strips of the page one wants to print. Come to think of it, handheld scanners can be improved by the laser location idea as well.

Embedded DOC pdf

When Microsoft Word exports to PDF, it would be nice if the original .doc file were embedded in the comments of the PDF so that the PDF is effectively editable by extracting the original. Similarly, I suppose, with LaTeX, DVI, and OpenOffice.

GF(13) digit permutation

case d in (0..4): p=d+1; d in (5..9): p=d+2; v=Mod(e,13)^p return v-2 where e in {2,6,7,11}; //e==2 maps 3 to 3

E-mail date

E-mail should have a date header corresponding to the date of the event being advertised for automatic calendar interfacing.

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

AES256

AES-256 is trivially breakeable by chosen plaintext attack in 2^128 work by enumerating all possible 128-bit input blocks.

Galois FFT

How do Discrete Fourier and Cosine Transforms behave in finite fields, such as GF(2^8)?

Cullen Primes

On August 23, 2005, Mark Rodenkirch found the largest known Cullen prime, 1354828*2^1354828+1.

rpmbuild dkms nvidia

rpmbuild --rebuild dell-nvidia-6624-1dkms.src.rpm

rpm -Uvh /usr/src/redhat/RPMS/i386/dell-nvidia-6624-1dkms.i386.rpm

be sure kernel-devel or kernel-smp-devel is installed.

Firefox shift click select

Click one point on a firefox page. Do not drag. Shift-click somewhere else. The region betwen is selected.

A day's work

gnome-panel gaim-otr owl

plus backups, purging most files, chsh, xemacs sumo package install. up next: pbzip2

What I dislike about Metacity

...coming from Sawfish. Some of these problems may be fixable by configuration; then again, metacity is notoriously unconfigurable.

I want opaque cycle-windows (alt-tab) and opaque move-window and resize-window.

(custom-set-keymap (quote window-keymap) (quote (keymap (raise-or-pass-through-click . "Button1-Click") (resize-window-interactively . "M-Button3-Move") )))

Note that raise-or-pass-through-click is different from raise-and-pass-through-click.

(bind-keys global-keymap "F5" '(display-window (get-window-by-name-re "Mozilla") ))

Can't let windows go beyond the top edge of the screen (intentionally hiding the titlebar).

Encrypted mailing list links

http://sourceforge.net/projects/mmreencrypt/ http://www.rediris.es/app/pgplist/index.en.html http://www.synacklabs.net/projects/crypt-ml/

http://www.atnf.csiro.au/people/rgooch/PGPsendmail.html http://www.raphinou.com/smailman/smailman.html

windowmanger escape key

I wish there were a window manager escape key, which signals "I want to talk to the window manager now, not the application that has focus." The entire keyboard becomes available after the escape, enabling a vast palette of window manipulation operations ("restore the window arrangement to the one I named foobar"). On a Kinesis, I might bind the windowmanager escape key to the footswitch.

Search images on day

Assuming people set the clocks on their digital cameras (ha ha) correctly (ha ha), someone like Google could offer Image Search for photos taken on a certain day, by using EXIF information on jpegs. Or the camera can get the time from the cell network, or GPS, etc.

Someday, cameras will do GPS (some cell phones with cameras already have GPS, though I don't know if the encode the location information into the metadata) and we can search for all photos taken near a certain location at a certain time (and GPS can automatically get the correct time, too).

When Big Brother has us all get chips embedded in our skulls, and tracks our location via satellite, one could cross reference the people location data with the camera location (at a given point in time) to automatically identify people in a photograph. Or the camera could directly ping the Big Brother chips. These Big Brother chips could be the cell phones we already all carry around that record location at low resolution, or some Bluetooth variant.

JPEG tools

jpegtran does lossless rotations of jpeg images. The beta version, codenamed "croppatch" does lossless cropping, too.

jhead can extract the EXIF metadata from jpg and tif files.

knoppix tohd

The "tohd=/dev/hdb7" cheatcode rules! (As I have a flaky CD-ROM drive (Creative) that fails to read the CD occasionally.)

pi-th root of unity and Tan 1

While thinking about the "Pith root of unity", I found (cos 1)+(sin 1)i which is actually the (2*pi)-th root of unity. The one-radian angle marks out an equilateral wedge: both straight segments and the curved part are all the same length. Whereas sin(1) and and cos(1) are not especially interesting continued fractions, their ratio, the tangent of 1 radian, the slope of the ray to the 2*pi-th root of unity, does have a regular continued fraction:

In[3]:= ContinuedFraction[Tan[1],100]

Out[3]= {1, 1, 1, 3, 1, 5, 1, 7, 1, 9, 1, 11, 1, 13, 1, 15, 1, 17, 1, 19, 1, 21, 1, 23, 1, 25, 1, 27, 1, 29, 1, 31, 1, 33, 1, 35, 1, 37, 1, 39, 1, 41, 1, 43, 1, 45, 1, 47, 1, 49, 1, 51, 1, 53, 1, 55, 1, 57, 1, 59, 1, 61, 1, 63, 1, 65, 1, 67, 1, 69, 1, 71, 1, 73, 1, 75, 1, 77, 1, 79, 1, 81, 1, 83, 1, 85, 1, 87, 1, 89, 1, 91, 1, 93, 1, 95, 1, 97, 1, 99}

P2P filesystem

AFS or NFS backed by bittorrent instead of servers, with aggressive local disk caching, onto which is installed all of Debian.

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

Two-finger typing

For mobile devices: Partition the alphabet into two halves, minimizing the number of consecutive letters typed in each half.

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

Average change

On average, you get back 2 pennies, 0.4 nickles, 0.8 dimes, 1.5 quarters, or 50 cents; a ratio of 5:1:2:3.75.

baseball

What is the speed of a baseball as it comes off a baseball bat?

Interestingly, most baseballs are pitched faster than terminal velocity (75 mph)

basketball

What would basketball be like if points were awarded according to distance of shot? Again, computer vision to calc release points.

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

Boxing

What would boxing be like if computer vision was used to measure the speed and force of each punch?

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

vc-cancel-version and RCS branch

I'm finding the vc-cancel-version command in xemacs (I think it runs rcs -o) quite cool.

I suppose I will cry when I accidentally cancel a version I didn't want to cancel.

It would be cooll if instead of saying version 1.4 and 1.5 never existed, it would instead make 1.4 and 1.5 a branch off of 1.3.

Damnsmalllinux Right Alt Key

xmodmap -e "remove mod4 = Mode_switch"
xmodmap -e "keycode 108 = Alt_R"
xmodmap -e "add mod1 = Alt_R"

letters in alphabetical order

"almost" is one of the (many) longest words with the letters in alphabetical order. "wronged" is the longest (one of many) in reverse alphabetical order.

Collatz images

The 3X+1 3N+1 problem. Also see TOS.

Binary representations of the numbers. Shifting the image right when dividing by two.

1038743969413717663

1236472189813512351

46785696846401151

Fib-359

M127

M521

alphabet

What assignment of letters to numbers on a phone keypad is optimal, when predictive typing is used?

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

Theographein

Biology is more the study of the effects of evolution; is mathematics the writing of God? Or is it, too, naturally designed?

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

LISP editor

Color coded parentheses. Also parentheses of different shapes, ie, square bracket = french quotes, etc, but auto matched.

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

compiling hat with ghc 6.4 on debian

$ make
...
MkProg: hmake: the compiler 'ghc' is not known.

Stop - hmake dependency error.
$ locate hmakerc
/var/lib/hmake/debian/hmakerc
$ hmake-config `locate hmakerc` list
Global config file is:
    /var/lib/hmake/debian/hmakerc
Known compilers:
    ghc6        (6.4)
    /usr/bin/haskell-compiler   (6.4)
    /usr/bin/ghc6       (6.4)
Default compiler:
    /usr/bin/haskell-compiler
$ hmake-config new
hmake-config: Starting new personal config file in
.../.hmakerc/debian
$ hmake-config add ghc

GIF with transparancy to white background

giftopnm --alpha=$file.alpha $file > $file.ppm
pnminvert $file.alpha|pnmcomp -alpha=$file.alpha $file.ppm > $file.pnm

compress reorder lines

How well can one compress a file if one is allowed to put the records in any order?

lesskey

echo "\kl prev-file\n\kr next-file" | lesskey -

Optimal coinage

What set of 4 coins values optimize the average number of coins needed to make change from zero to 99? 3 coins from 0 to 19? Under the constraint that greedy change-making work?

Kerberos for Mac OS X

If Kerberos is not configured yet on Mac OS X (osx macos macosx) 10.4 (tiger) you'll get "debug1: Miscellaneous failure Server not found in Kerberos database" from ssh -v. The documentation at MIT Kerberos for Mac is mostly useful, but it neglects to mention that one one needs to touch a zero byte file "edu.mit.Kerberos" in /Library/Preferences in order for the "Edit Realms..." menu option in the Edit Menu to work.

It's a little unnerving that the default settings are for 7-day renewable tickets.

qsort madness

qsort() (redhat glibc 2.3.2-95.30) attempts to be clever with memory by switching to a different algorithm for large inputs. On my computer, the threshold is at 131459071-131459072 for 4-byte integers. Performance abruptly degrades at the threshold. It also has the unfortunate bug-hiding effect that programs can work properly with the small algorithm and fail when inputs get large enough. Finally, at large inputs, the C++ STL implementation becomes comparable. Here are some counts to the number of calls to the comparison function for an array initialized by a[0]=1 a[n+1]= a[n]*1664525+1013904223

qsort
 131459070 easy  0        hard 3333417997
 131459071 easy  0        hard 3333417454
 131459072 easy  50294519 hard 4063553331
 268435456 easy 102684870 hard 8680917338

C++ STL sort()
 131459070 easy 15139169 hard 4345836000
 131459071 easy 15141479 hard 4316599909
 131459072 easy 15139606 hard 4470743742
 268435456 easy 30917419 hard 9444799480

The columns give the number of "easy" comparisons (pa==pb for qsort; a==b for sort) and "hard". The PRNG has period 2^32 so every number is unique.

Fastest Orbit

How long does it take for a satellite to orbit the earth just above the surface? The sun? Mumble gravity=centripetal force...

Nontranscendentals

Continued fractions can tell if a number is rational or a quadratic surd. Is there analogous for all algebraic?

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

Self referential math

Simple Continued Fraction Expansion of Khinchin's Constant

Khinchin's constant digits

Energy game

Suppose teams have "energy points" to allocate to games through the season. When two teams play each other in a game, the team which had allocated more energy points will win. The teams all play against each other, in some variation of round robin. The goal is to finish the season with the best record.

Lots of variations: whether all games are played simultaneously, whether teams all begin with the same number of energy points, the outcome of each game is probabilistic on the difference or ratio of energy points, imperfect information of how many energy points the opposing team has, or started off with, or used in previous games. With unequal initial energies, the goal might be to finish with a better record than teams with greater initial energies.

Voice bookmarks

Let web bookmarks be accessed a recorded voice tag, much like voice activated dialing on cell phones.

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

Game of Y

Does the game of Y necessarily have to have a winner?

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

Translation from latin-1 to ASCII

Latin-1 (ISO 8859-1):
tr![\xc0-\xff]![AAAAAAECEEEEIIIIDNOOOOO*OUUUUYTsaaaaaaeceeeeiiiidnooooo/ouuuuyty]!;
Getting rid of those accents.

Modern cattle

What is a modern version of Archimedes's cattle problem? A problem which will require 2,000 years to solve.

Part I of the cattle problem was a set of linear Diophantine equations; Part II added quadratic Pell-equation constraints. A modern extension might add cubic elliptic-curve constraints.

Alternatively, factoring F12 will probably take on the order of 2000 years.

update: "An unusual cubic representation problem" by Andrew Bremner and Allan MacLeod.

Certicom ECC order factorizations

just some unformatted notes of the harder ones.

862591559561497151050143615844796922676745216137584527768676481602284639 solution 3 [2, 1; 241, 1; 13633, 1; 5550215053208003929302852601201, 1; 23651403663025001450257295998140623, 1]

15450938044564692288746582873614059390629490453344209663962540632677447295745316740045672843724365195742523 solution 4 [2, 1; 41, 1; 24639539179251210855889, 1; 227011624723863689126629, 1; 4549697311286994681589117379, 1; 7404194459971394608150930435979, 1]

? m[5] %5 = 587135645693458306972370149197334256843920637227079966811081824609485917244124494882365172478748165648998663

[2, 1; 17, 1; 239, 1; 359, 1; 9137, 1; 52195183, 1; 3544939683290142715349, 1; 119048596986995103937710155160761091324964506194606913025949983644817, 1]

? m[6] %5 = 815061317237192195822186322581994619328922585201839922566836546496458006742605076478278502538607299555033837 [2, 2; 3, 2; 22640592145477560995060731182833183870247849588939997849078792958234944631739029902174402848294647209862051, 1] [2, 1; 5, 2; 289729071978852212063521, 1; 1562880244694956534724744409145689309637193746299406076190301328929803286807967321, 1] [2, 3; 5, 1; 7, 2; 11, 1; 19, 1; 109, 1; 35002321230253561971279870916994230549204397557833418203638668836315513707, 1] [2, 1; 54934487254227589231, 1; 6079857359179201369147, 1; 52399649852849583985441933671329, 1]

Elliptic Curves with Pari/GP

From the example in section 3.1.2 in the Certicon ECC Challenge.

? t=Mod(1,2)
%1 = Mod(1, 2)
? p1=t*x^4+t*x+t
%2 = Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)
? polisirreducible(p1)
%124 = 1
? a=Mod(t*x+t,p1)
%3 = Mod(Mod(1, 2)*x + Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2))
? tt=Mod(t,p1)
%4 = Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2))
? e=ellinit([tt,a,0,0,tt])
%5 = [Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2)*x+ Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), 0, 0, Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(0, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(0, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), 0, 0, 0, 0, 0, 0]
? a1=[Mod(t*x^3+t*x^2,p1),Mod(t*x^2+t,p1)]
%6 = [Mod(Mod(1, 2)*x^3 + Mod(1, 2)*x^2, Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2)), Mod(Mod(1, 2)*x^2 + Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2))]
? ellisoncurve(e,a1)
%7 = 1
? elladd(e,a1,a1)
%8 = [Mod(Mod(1, 2)*x^2 + Mod(1, 2)*x + Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x+ Mod(1, 2)), Mod(Mod(1, 2)*x^2 + Mod(1, 2), Mod(1, 2)*x^4 + Mod(1, 2)*x + Mod(1, 2))]
? q=[0,tt];
? for(pw=1,3,q1=q;
? for(i=1,length(q1),q1[i]=q1[i]+Mod(t*x^pw,p1));q=concat(q,q1))
for(ea=1,length(q), for(ec=2,length(q), e=ellinit([tt,q[ea],0,0,q[ec]]);listkill(l);for(i=1,length(q), for(j=1,length(q), if(ellisoncurve(e,[q[i],q[j]]),listput(l,[q[i],q[j]]))));print(ea-1," ",ec-1," ",length(l)+1)))
? for(s=1,length(l), for(i=1,length(l)+1, if([0]==ellpow(e,l[s],i),print(s," ",i);break)))

It's unfortunate the output is so messy.

chase's blog - Fastback Inside!

Instantaneous Back and Forward buttons on your browser. New preference browser.sessionhistory.max_viewers 5.

Decoding certificates

$ wget http://bs.mit.edu/mitca.ca
--00:02:56-- http://bs.mit.edu/mitca.ca
=> `mitca.ca'
Resolving bs.mit.edu... 18.7.21.84
Connecting to bs.mit.edu[18.7.21.84]:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 617 [application/x-x509-ca-cert]

100%[====================================>] 617 --.--K/s

00:02:56 (5.88 MB/s) - `mitca.ca' saved [617/617]

$ openssl x509 -inform DER -text -in mitca.ca -noout
Certificate:
Data:
Version: 1 (0x0)
Serial Number: 0 (0x0)
Signature Algorithm: md5WithRSAEncryption
Issuer: C=US, ST=Massachusetts, O=Massachusetts Institute of Technology, OU=MIT Certification Authority
Validity
Not Before: Jul 15 20:23:00 1996 GMT
Not After : Jul 13 20:23:00 2006 GMT
Subject: C=US, ST=Massachusetts, O=Massachusetts Institute of Technology, OU=MIT Certification Authority
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public Key: (1024 bit)
Modulus (1024 bit):
00:d3:d0:eb:e7:51:b5:33:75:a6:d8:a3:84:ea:02:
70:5c:cf:9c:20:e0:0b:03:8b:8e:46:6e:15:25:e1:
77:f6:6b:c4:70:dd:d4:16:0b:cc:11:88:31:38:0b:
ee:7c:59:24:57:e9:8d:cd:75:f8:52:63:dd:33:0c:
f0:4f:9f:b5:fc:91:ae:32:85:8c:1a:75:63:19:98:
86:1e:92:23:b2:87:f3:f5:c9:a6:a2:97:68:f2:ec:
b2:1a:ad:b3:f5:ed:09:ea:cc:e7:bc:b4:64:50:15:
e6:57:00:1a:7a:c6:de:fe:e1:30:58:5a:5d:ab:bb:
b4:1c:11:ec:64:c1:d3:a4:55
Exponent: 65537 (0x10001)
Signature Algorithm: md5WithRSAEncryption
01:19:13:24:13:13:28:10:db:54:0d:00:24:18:ca:02:35:27:
af:bb:39:03:c5:e2:76:b9:7b:49:f9:1d:91:cb:52:fd:b6:09:
52:c4:ed:73:93:37:37:e2:cc:6f:18:a8:3f:47:9e:16:c6:60:
31:81:3a:21:7f:f8:27:05:2a:88:e6:51:0d:ae:24:32:b9:c5:
6a:04:02:be:4f:60:95:d2:82:92:6a:ec:65:0c:54:39:5b:54:
74:52:a2:85:6c:80:be:4d:29:f3:75:be:e0:d5:80:70:6b:dc:
39:5a:13:68:c6:ec:0e:87:b7:31:26:26:56:2d:86:bb:4c:80:
7b:43
$ bc
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
ibase=16
00D3D0EBE751B53375A6D8A384EA02\
705CCF9C20E00B038B8E466E1525E1\
77F66BC470DDD4160BCC118831380B\
EE7C592457E98DCD75F85263DD330C\
F04F9FB5FC91AE32858C1A75631998\
861E9223B287F3F5C9A6A29768F2EC\
B21AADB3F5ED09EACCE7BCB4645015\
E657001A7AC6DEFEE130585A5DABBB\
B41C11EC64C1D3A455

14874232348041148870879819006215632592626006624089886671166071398570\
02103995689503190533069669831630135040326377461588598729653631965144\
40766020608225910888987591998289529837389575629713521989417386401506\
78089276107148587284179435836431649958136516334321733549452470076311\
2519694607834206454009153643273757781
quit
$ t=14874232348041148870879819006215632592626006624089886671166071398570\
02103995689503190533069669831630135040326377461588598729653631965144\
40766020608225910888987591998289529837389575629713521989417386401506\
78089276107148587284179435836431649958136516334321733549452470076311\
2519694607834206454009153643273757781

> > > > $ $
$ /afs/sipb.mit.edu/project/pari-gp/arch/i386_rh9/bin/gp
GP/PARI CALCULATOR Version 2.1.5 (released)
i686 running linux (ix86 kernel) 32-bit version
(readline v4.2 enabled, extended help available)

Copyright (C) 2002 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

realprecision = 28 significant digits
seriesprecision = 16 significant terms
format = g0.28

parisize = 4000000, primelimit = 500000
? \g5
debug = 5
? factorint(148742323480411488708798190062156325926260066240898866711660713985700210399568950319053306966983163013504032637746158859872965363196514440766020608225910888987591998289529837389575629713521989417386401506780892761071485872841794358364316499581365163343217335494524700763112519694607834206454009153643273757781)
Miller-Rabin: testing base 1000288896
IFAC: cracking composite
148742323480411488708798190062156325926260066240898866711660713985700210399568950319053306966983163013504032637746158859872965363196514440766020608225910888987591998289529837389575629713521989417386401506780892761071485872841794358364316499581365163343217335494524700763112519694607834206454009153643273757781
IFAC: checking for pure square
OddPwrs: is 148742323480411488708798190062156325926260066240898866711660713985700210399568950319053306966983163013504032637746158859872965363196514440766020608225910888987591998289529837389575629713521989417386401506780892761071485872841794358364316499581365163343217335494524700763112519694607834206454009153643273757781
...a 3rd, 5th, or 7th power?
modulo: resid. (remaining possibilities)
211: 86 (3rd 1, 5th 0, 7th 0)
209: 6 (3rd 0, 5th 0, 7th 0)
IFAC: trying Pollard-Brent rho method first
Rho: searching small factor of 1024-bit integer
Rho: using X^2+1 for up to 49152 rounds of 32 iterations
Rho: time = 73790 ms, 24576 rounds
Rho: fast forward phase (8192 rounds of 64)...
Rho: time = 34590 ms, 32772 rounds, back to normal mode
Rho: time = 19330 ms, 40960 rounds
Rho: time = 19490 ms, Pollard-Brent giving up.
IFAC: trying Shanks' SQUFOF, will fail silently if input
is too large for it.
IFAC: trying Lenstra-Montgomery ECM
ECM: working on 64 curves at a time; initializing for up to 400 rounds...
ECM: time = 0 ms
ECM: dsn = 12, B1 = 1800, B2 = 198000, gss = 128*420
ECM: time = 73080 ms, B1 phase done, p = 1801, setting up for B2
ECM: time = 1300 ms, entering B2 phase, p = 2017
ECM: time = 45340 ms
ECM: dsn = 14, B1 = 2200, B2 = 242000, gss = 128*420

Some factorization problems (and solutions)

Long strings of zeros and nines compress well.

g= [10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 22, 23, 25, 27, 29, 32, 34, 37, 40, 43, 46, 50, 54, 58, 63, 68, 74, 79, 86, 93 ] ; for(i=1, 307, for(j=1, 30, s=(g[j]*10^i); a=precprime(s); b=nextprime(2*s); c=a*b; lc=log(c); print(ceil(lc/log(2)), " ", ceil(lc/log(10)), " ", c, " ", g[j], "*10^", i, a-s)))

ECC DOF

Elliptic Curve Cryptography, on the field GF(2^m), appears to have 4 degrees of freedom: The reduction polynomial of the field, the fixed point P, and the curve parameters a and b.

exp exp exp exp 1

I calculated the 1,656,521-digit number e^e^e^e = exp(exp(exp(exp(1)))). The digits surrounding the decimal point are: ... 4,745,087,021.2212029997 ...

The entire number is e^e^e^e here.

Large-print LaTeX

In Acrobat Reader, open this document in View | Continuous - Facing, and Maximize the window size. You should be able to read the text comfortably. This is the One True Solution to the "monitors are landscape but paper is portrait; people like to read narrow columns not wide screens" problem.

\usepackage{type1cm} \setlength{\topmargin}{-0.5in} \setlength{\oddsidemargin}{-0.5in} \setlength{\evensidemargin}{-0.5in} \setlength{\textwidth}{7.5in} \setlength{\textheight}{9in} \setlength{\footskip}{0in} \makeatletter \renewcommand\Huge{\@setfontsize\Huge{49.76}{60}} \renewcommand\LARGE{\@setfontsize\LARGE{34.56}{44}} \renewcommand\Large{\@setfontsize\Large{28.8}{36}} \renewcommand\footnotesize{\@setfontsize\footnotesize{16}{19}} \renewcommand\huge{\@setfontsize\huge{41.48}{50}} \renewcommand\large{\@setfontsize\large{24}{28}} \renewcommand\normalsize{\@setfontsize\normalsize{20}{24}} \renewcommand\scriptsize{\@setfontsize\scriptsize{14}{16}} \renewcommand\small{\@setfontsize\small{18}{22}} \renewcommand\tiny{\@setfontsize\tiny{10}{12}} \makeatother

flight delays

New York and Newark airports are having delays because other airports are not having delays. Too much volume.

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

On the NSA

The National Security Agency (Information Assurance Directorate) has had quite a good track record in being ahead of the curve in foreseeing crytoanalytic breaks. DES had its S-boxes strengthed against an attack unknown at the time. DES has yet to be broken, except by brute force. As DES key strength became too small, they introduced Triple-DES, also yet to be broken. Skipjack is also yet to be broken, though it was ``almost'' (N-1 rounds in X/2 work.) SHA-0 got replaced by SHA-1 before SHA-0 was broken, and SHA-2 (aka SHA-256, SHA-384, SHA-512) has been available for a while by the time SHA-1 was broken recently. One can also tell the story that they foresaw the MD4 and MD5 breaks and the SHA series were a response.

What of the future? I think they currently recommend AES-256 for Top Secret communications, and elliptic curve cryptography for crytographic signing. Are there breaks for AES-128, AES-192, RSA, and regular DH on the horizon?

Mozilla popup location bars, menu bars, etc.

Go to about:config and edit dom.* to prevent popup windows from hiding the menu bar, scroll bar, location bar, etc.

FFT

Power Spectrum of some synthetic hash table performance stuff

Two MD5 Challenges

Find a preimage to the all-zeros checksum. Find a second preimage that has the same checksum as the zero-byte string.

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

encrypt one bit

How many bits does it take to transmit one bit, authenticated, with secret-key encryption?

ld relocation error R_SPARC_DISP32 gcj

If you forget --disable-multilib in a solaris compile of gcc, this is what happens (during java)

/bin/sh ./libtool --tag=GCJ --mode=link /BUILD/gcc/gcj -B/BUILD/sparc-sun-solaris2.9/sparcv9/libjava/ -B/BUILD/gcc/ -L/BUILD/sparc-sun-solaris2.9/sparcv9/libjava -g -O2 -m64 -m64 -o jv-convert --main=gnu.gcj.convert.Convert -rpath /INSTALL/lib/sparcv9 -shared-libgcc -L/BUILD/sparc-sun-solaris2.9/sparcv9/libjava/.libs libgcj.la

/BUILD/gcc/gcj -B/BUILD/sparc-sun-solaris2.9/sparcv9/libjava/ -B/BUILD/gcc/ -g -O2 -m64 -m64 -o jv-convert --main=gnu.gcj.convert.Convert -shared-libgcc -L/BUILD/sparc-sun-solaris2.9/sparcv9/libjava -L/BUILD/sparc-sun-solaris2.9/sparcv9/libjava/.libs ./.libs/libgcj.a -L/BUILD/sparc-sun-solaris2.9/sparcv9/libstdc++-v3/src -L/BUILD/sparc-sun-solaris2.9/sparcv9/libstdc++-v3/src/.libs -lpthread -lrt -ldl -L/BUILD/gcc/sparcv9 -L/BUILD/gcc -L/usr/ccs/bin/sparcv9 -L/usr/ccs/bin -L/usr/ccs/lib/sparcv9 -L/usr/ccs/lib -L/lib/sparcv9 -L/usr/lib/sparcv9 -lgcc -lgcc -Wl,-R -Wl,/INSTALL/lib/sparcv9

ld: fatal: relocation error: R_SPARC_DISP32: file ./.libs/libgcj.a(prims.o): symbol : offset 0xffffffff722fbc71 is non-aligned

ld: fatal: relocation error: R_SPARC_DISP32: file ./.libs/libgcj.a(prims.o): symbol : offset 0xffffffff722fbc91 is non-aligned

ld: fatal: relocation error: R_SPARC_DISP32: file ./.libs/libgcj.a(jni.o): symbol : offset 0xffffffff722fbeb9 is non-aligned

...etc.

I am using the patched binutils 2.15 as described in http://gcc.gnu.org/install/specific.html in the *-*-solaris2* section. The --disable-multilib flag is in that document, too.

Blog Template CSS changes

--- Ken's blog.html	2005-04-10 13:43:05.000000000 -0400
+++ j.html	2005-04-10 13:41:46.000000000 -0400
@@ -94,17 +94,17 @@
 /* Content
 ----------------------------------------------- */
 #content {
-  width:660px;
   margin:0 auto;
   padding:0;
   text-align:left;
   }
 #main {
-  width:410px;
+  width:70%;
   float:left;
+  margin-left: 2em;
   }
 #sidebar {
-  width:220px;
+  width:20%;
   float:right;
   }

BitTorrent Poisoning Attack

Suppose an adversary with 10,000 to 100,000 machines wanted to poison a BitTorrent torrent with bogus files (spoofed files). Because BitTorrent has hashed pieces (the hashes stored in the metainfo file), this would be an attack of bogus pieces (spoofed pieces). A hacked node would advertise (to the tracker) that it has a piece but distribute bogus pieces.

To combat such an attack we would want to know quickly whether a piece was bogus, quicker than downloading the entire piece and checking the hash. Typically a BitTorrent piece is 256 KiB. For a 640MB CD-image, there 2,500 256KiB pieces, each with a 20 byte SHA-1 checksum for a torrent metainfo file of about 50 KiB.

Ideally, we want hashes at a much finer resolution, but that makes the metainfo file a lot larger. The key idea is to distribute the high-resolution file of hashes itself through BitTorrent, and do so recursively. This is very roughly the idea of Merkle Hash Trees to be part of the BitTorrent 2 (BT2) protocol.

Assume a 1 GiB file. If each 6,464-byte is hashed with a 64 byte SHA-512 (SHA2) checksum, there's 9,900,990 bytes of first-level overhead. To transfer this 9.9 MiB of hashes, we use the BitTorrent (still under attack from the spoofing adversary) we hash each 6,464 byte chunk with SHA-512 for an additional 98,029 bytes of second-level overhead. Recursing again, the third-level file of hashes is 970 bytes. The sum of the infinite series is 10 MiB, or 1% of the original 1 GiB file. The chunk size 6,464 was chosen for one-percent overhead; obviously tweakable for different overheads and checksum widths.

For downloading, the metainfo file need only contain the ``root'' checksum, and first the client would download the depth-1 portion of the hash tree. This should be easy because it's the first thing everyone downloads, so there should be lots of copies. Then using the hashes of the depth-1 level, download the next level, eventually working to the leaves which contain the actual data, in 6,464 byte chunks.

We assume no propagation of information of what peers are bad, because that is a hard problem. (Who do you trust?)

One assumes it is worth it to waste 6,464 bytes of download to mark that a particular peer (an IP / port tuple?) is bad. With 100,000 bad nodes however, that's up to 646,400,000 bytes of wasted communication. Furthermore, during the time it takes to test all those bad nodes, the adversary can change IP addresses. Ugh.

Probabilistically, though, assume the adversary only has resources to create a 100:1 bad-node to good-node ratio (this is still a tremendous number of nodes for popular files which my have hundreds or thousands of real downloaders, i.e., good nodes). Assuming a swarm size of 20, we need to ask 2,000 machines to find 20 good nodes, so wasted communication of 1980*6464=12.8 MiB of wasted communication.

South San Francisco The Industrial City

Signhill park

Complementing IUPAC Nucleotide codes

y/[ABCDGHKMNRSTVWY]/[TVGHCDMKNYSABWR]/

Emacs Mule

from Emacs help:

C-x RET f runs the command set-buffer-file-coding-system which is an interactive compiled Lisp function in `international/mule'. (set-buffer-file-coding-system CODING-SYSTEM &optional FORCE)

Set the file coding-system of the current buffer to CODING-SYSTEM. This means that when you save the buffer, it will be converted according to CODING-SYSTEM. For a list of possible values of CODING-SYSTEM, use M-x list-coding-systems.

If the buffer's previous file coding-system value specifies end-of-line conversion, and CODING-SYSTEM does not specify one, CODING-SYSTEM is merged with the already-specified end-of-line conversion.

If the buffer's previous file coding-system value specifies text conversion, and CODING-SYSTEM does not specify one, CODING-SYSTEM is merged with the already-specified text conversion.

However, if the optional prefix argument FORCE is non-nil, then CODING-SYSTEM is used exactly as specified.

This marks the buffer modified so that the succeeding C-x C-s surely saves the buffer with CODING-SYSTEM. From a program, if you don't want to mark the buffer modified, just set the variable `buffer-file-coding-system' directly.

from C-x RET C-h

Global Bindings Starting With C-x RET:
key             binding
---             -------

C-x RET l       set-language-environment
C-x RET c       universal-coding-system-argument
C-x RET C-\     set-input-method
C-x RET X       set-next-selection-coding-system
C-x RET x       set-selection-coding-system
C-x RET p       set-buffer-process-coding-system
C-x RET k       set-keyboard-coding-system
C-x RET t       set-terminal-coding-system
C-x RET f       set-buffer-file-coding-system

Topping top in Solaris 8 with prstat

Topping top in Solaris 8 with prstat: Sun's equivalent of "top".

Hard Drives with Lifetime Warranty

I wonder how much of a price premium people would be willing to pay for a hard drive with a lifetime warranty?

glimpseindex fun

Indexing 149,000 mail messages totaling 1.21 GB took 7 hours with glimpseindex -o. The total size of the .glimpse_* index files is 368 MB. After bzip2 compression, the messages themselves are 420 MB and the index files (surprisingly) compress by 50% to 182 MB.

Circle polygons

What are polygons all of whose vertices lie on the circumcircle? Similarly for edges on the incircle? Similarly for polyhedra?

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

Misère hex

The grave accent goes on the second e. Search misere hex without the accent. I'd like to see a computer program that plays (aka) "Rex" well.

Math fonts

By dropping the fonts from the symfont fix package into ~/.fonts, one can view pages like Mathematical Constants and Computation, Perimeter of an Ellipse, and pages converted by T_TH. I still don't fully understand why the font gets recognized as iso8859-1, even though the EncodingScheme is ``FontSpecific''. One also needs to use a ``recent'' (probably GTK2+) build of Firefox or Mozilla, the kind that try to do antialiased fonts. It might be necessary to run fc-cache to generate the index files.

jsMath displays some awesomely rendered mathematics. drop the BaKoMa Tex fonts into ~/.fonts. The fonts are supposedly also available at CTAN and mozilla mathML

inch centimeter 127

In the olden days, the centimeter was defined in terms of the inch: 10000/3937, but now the inch is defined in terms of the centimeter: 254/100. It's interesting how 127 divides both 3937 and 254.

Firefox extensions

Tried a bunch of Firefox extensions. FlashGot's build gallery feature is cool, once I figured out how to get it to work. It would be nice if it could work on all links on the page. It gets confused by HTML entities, e.g., %20 for space. Thumbs is nice in the unusual case that every linked HTML page has a picture on it. Down Them All was usable. All-in-one gestures is nice when I remember to use the gestures. Clusty works correctly in the canonical example of "saturn" (but is useful as a website). Linky is cool, as is GoogleBar's "reverse link" search. Coralize this link extension is great.

How to memorize 81 bits

Color each grid square by the bit, and remember the shape of the bits, and the letters they correspond to.

yo car caul
ga pet dron
ex sho ambi
ot wer dext
ic ing rous
an con
ti fig  e  van
bo ura  du  it
dy ble  cat  y
        ions

Scroll-wheel app-switcher

Scroll the mouse-wheel on the desktop to switch (and cycle) between windows of running applications. (No window manager I know does this by default, yet.)

Factoring Ramanujan's Constant

exp(pi*sqrt(163)) = 262537412640768744 ( 2 2 2 3 10939058860032031 (2 3 5 7 13 179 (2 88 (2 2 2 11)) 6959 (2 7 7 71) 3216751 (2 3 5 5 5 4289 (2 2 2 2 2 2 67))))

Unsolved instance of the Post Correspondance Problem

{(10,0),(0,001),(001,1)} Ling Zhao's PCP page

Prove it has no solution...
Also given in bit-flipped form as (6.15) in his Master's thesis: {(110,1), (1,01), (0, 110)}

1- in Lisp is pred in Haskell

The handy function 1- in Lisp is pred in Haskell, also (subtract 1) and (-1) by operator lambdas.

RFC 2409, RFC 3526, and "bad" generators

The two RFCs specify 2 as a generator for the prime Diffie-Hellman fields. However, 2 is not a generator: for example:

RFC 2409 - The Internet Key Exchange (IKE)

6.1 First Oakley Default Group

FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF

? p=2^768-2^704-1+2^64*(floor(2^638*pi)+149686)
%41 = 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919
? isprime(p)
%42 = 1
? j=2;
? (p-1)%j
%44 = 0
? q=(p-1)/j;
? isprime(q)
%46 = 1
? Mod(2,p)^q
%47 = Mod(1, 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919)
? znprimroot(p)
%48 = Mod(7, 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919)

The reason is buried Appendix E of RFC 2412 (uncited): " Using 2 as a generator is efficient for some modular exponentiation algorithms. [Note that 2 is technically not a generator in the number theory sense, because it omits half of the possible residues mod P. From a cryptographic viewpoint, this is a virtue.]"

One wonders why they didn't use a multiplier (instead of 149686) for which 2 really is a number-theoretic generator.

Unfriendly primes

Reply from On-Line Encyclopedia

./x.primes-2.ll.x primes 10000 | drop.pl 4 | xargs -n1 -i expr '{}' - 1 | xargs -n1 factor | perl -nlwe 'BEGIN{$f{2}=0}($a,$b)=/(.*):.* (\d+)/;$a++;$f{$a}=$f{$b}+1;END{print "$f{$_} $_" for(keys %f)}' | sort +0n +1n | perl -nwae 'BEGIN{$p="-1"}print if $p!=$F[0];$p=$F[0]'

Better is
./x.primes-2.ll.x primes 2000000 | drop.pl 4 | xargs -i expr '{}' - 1 | xargs factor | perl -nlwae 'BEGIN{$f{2}=0}($a=$F[0])=~s/://;shift@F;$m=0;for(@F){if($f{$_}>$m){$m=$f{$_}}}$f{++$a}=$m+1;END{print "$f{$_} $_" for(keys %f)}' | sort +0n +1n | perl -nwae 'BEGIN{$p="-1"}print if $p!=$F[0];$p=$F[0]'
First difference is at 239 (238: 2 7 17).

./x.primes-2.ll.x primes 2000000000 | drop.pl 4 | xargs -i expr '{}' - 1 | xargs factor | perl -nlwae 'BEGIN{$f{2}=0;$x=0} ($a=shift@F)=~s/://;$m=0; for(@F){if($f{$_}>$m){$m=$f{$_}}} $f{++$a}=++$m;if ($m>$x){print $a;$x=$m}'

Memorizing 81 bits

Y O G A	C A R P E T	C A U L D R O N
E X O T I C	S H O W E R I N G	A M B I D E X T R O U S
A N T I B O D Y	C O N F I G U R A B L E	E D U C A T I O N S	V A N I T Y

Y O G A	C A R P E T	C A U L D R O N
E X O T I C	S H O W E R I N G	A M B I D E X T R O U S
A N T I B O D Y	C O N F I G U R A B L E	E D U C A T I O N S	V A N I T Y

Mersenne 42 in other bases

The 42nd known Mersenne prime 2^25964951-1 was discovered recently. The minus-one factorization of the exponent is 25964951 (5 5 11 17 2777 (2 2 2 347 (2 173 (2 2 43 (2 3 7))))).

2^25964951-1 in base 94

2^25964951-1 in base 52

The huge pages of ``random'' characters inspire the Word-search Problem: given a string S, and a target word T (or a list of target words), find T= S[a]S[b]S[c]... where the indices a,b,c... are in arithmetic progression.

IRC is an Internet Push Technology

One must query a RSS feed continuously to get real-time updates, which will usually get you banned (try the Coral distribution instead). Is there a better "push" solution?

Yes. IRC.

NIC GPS

What if all network cards had GPS receivers? They would provide the link between the physical and cyber worlds.

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

Electronic dissertations library

Electronic dissertations library

XML::Parser of RSS

I have drunk the XML Kool-aid, also the Perl References Kool-aid.

#!perl -wl
use XML::Parser;
use LWP::Simple;
$content=get("http://earthquake.usgs.gov/recenteqsww/catalogs/eqs1day-M2.5.xml");
my $xml=new XML::Parser(Style => 'Tree');
$f=$xml->parse($content);
exit unless $$f[0] eq 'rss';
@g=&findelement('channel',@$f[1]);
@items=&findelement('item',$g[0]);
for (@items) {
  @s=&findelement('dc:subject',$_);
  die unless @s==2;
  $mag=&intext($s[0]);
  $post=&intext($s[1]);
  $title=&gettext('title',$_);
  $link=&gettext('link',$_);
  $date=&gettext('description',$_);
  print "$title\n$date\n$link\n$mag $post\n";
}
sub findelement {
  my ($tag,$val);  my @ret;  my ($target,$arr)=@_;
  @_=@$arr;
  shift; #throw away attribute hash
  while (@_) {
    $tag=shift;    $val=shift;
    push @ret,$val if ($tag eq $target);
  }
  @ret;
}
sub gettext {
  my ($target,$arr)=@_;
  my @t0=&findelement($target,$arr);
  &intext(@t0);
}
sub intext {
  my @t1=&findelement('0',$_[0]);
  $t1[0];
}

Lossy conversion between decimal to binary

Suppose you have random decimal data, for example decimal digits of pi, and you want random bits. Take 28 digits at a time and get 93 bits out (2^93 = 0.99035e28), rejecting if the value is too large.

For the other direction, take 196 bits at a time and get 59 digits out. 2^196=1.004336e59.

1.66053886 yoctomoles

CODATA Value: atomic mass unit-kilogram relationship